Approximation and Online Algorithms [[electronic resource] ] : Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Selected Papers / / edited by Thomas Erlebach, Giuseppe Persiano |
Edizione | [1st ed. 2006.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 |
Descrizione fisica | 1 online resource (X, 349 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Software engineering
Algorithms Computer science—Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence—Data processing Software Engineering Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
ISBN | 3-540-32208-6 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | “Almost Stable” Matchings in the Roommates Problem -- On the Minimum Load Coloring Problem -- Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT -- The Hardness of Network Design for Unsplittable Flow with Selfish Users -- Improved Approximation Algorithm for Convex Recoloring of Trees -- Exploiting Locality: Approximating Sorting Buffers -- Approximate Fair Cost Allocation in Metric Traveling Salesman Games -- Rounding of Sequences and Matrices, with Applications -- A Note on Semi-online Machine Covering -- SONET ADMs Minimization with Divisible Paths -- The Conference Call Search Problem in Wireless Networks -- Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents -- Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost -- A Better-Than-Greedy Algorithm for k-Set Multicover -- Deterministic Online Optical Call Admission Revisited -- Scheduling Parallel Jobs with Linear Speedup -- Online Removable Square Packing -- The Online Target Date Assignment Problem -- Approximation and Complexity of k–Splittable Flows -- On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem -- Tighter Approximations for Maximum Induced Matchings in Regular Graphs -- On Approximating Restricted Cycle Covers -- A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs -- Speed Scaling of Tasks with Precedence Constraints -- Partial Multicuts in Trees -- Approximation Schemes for Packing with Item Fragmentation. |
Record Nr. | UNISA-996466153003316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation and Online Algorithms [[electronic resource] ] : Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Selected Papers / / edited by Thomas Erlebach, Giuseppe Persiano |
Edizione | [1st ed. 2006.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 |
Descrizione fisica | 1 online resource (X, 349 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Software engineering
Algorithms Computer science—Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence—Data processing Software Engineering Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
ISBN | 3-540-32208-6 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | “Almost Stable” Matchings in the Roommates Problem -- On the Minimum Load Coloring Problem -- Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT -- The Hardness of Network Design for Unsplittable Flow with Selfish Users -- Improved Approximation Algorithm for Convex Recoloring of Trees -- Exploiting Locality: Approximating Sorting Buffers -- Approximate Fair Cost Allocation in Metric Traveling Salesman Games -- Rounding of Sequences and Matrices, with Applications -- A Note on Semi-online Machine Covering -- SONET ADMs Minimization with Divisible Paths -- The Conference Call Search Problem in Wireless Networks -- Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents -- Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost -- A Better-Than-Greedy Algorithm for k-Set Multicover -- Deterministic Online Optical Call Admission Revisited -- Scheduling Parallel Jobs with Linear Speedup -- Online Removable Square Packing -- The Online Target Date Assignment Problem -- Approximation and Complexity of k–Splittable Flows -- On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem -- Tighter Approximations for Maximum Induced Matchings in Regular Graphs -- On Approximating Restricted Cycle Covers -- A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs -- Speed Scaling of Tasks with Precedence Constraints -- Partial Multicuts in Trees -- Approximation Schemes for Packing with Item Fragmentation. |
Record Nr. | UNINA-9910483079503321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation and Online Algorithms [[electronic resource] ] : Second International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004, Revised Selected Papers / / edited by Giuseppe Persiano, Roberto Solis-Oba |
Edizione | [1st ed. 2005.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 |
Descrizione fisica | 1 online resource (VIII, 295 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence—Data processing Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Online Packet Switching -- Approximation Algorithms for Mixed Fractional Packing and Covering Problems -- Regular Papers -- Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-Trees -- Online Bin Packing with Resource Augmentation -- A PTAS for Delay Minimization in Establishing Wireless Conference Calls -- This Side Up! -- Approximation Algorithm for Directed Multicuts -- Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria -- Approximation Algorithms for Spreading Points -- More Powerful and Simpler Cost-Sharing Methods -- Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints -- Priority Algorithms for Graph Optimization Problems -- Pricing Network Edges to Cross a River -- Submodular Integer Cover and Its Application to Production Planning -- Stochastic Online Scheduling on Parallel Machines -- A -Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path -- Order-Preserving Transformations and Greedy-Like Algorithms -- Off-line Admission Control for Advance Reservations in Star Networks -- Joint Base Station Scheduling -- Universal Bufferless Routing -- Strong Colorings of Hypergraphs -- Deterministic Monotone Algorithms for Scheduling on Related Machines -- Better Bounds for Minimizing SONET ADMs. |
Record Nr. | UNISA-996465950503316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation and Online Algorithms [[electronic resource] ] : Second International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004, Revised Selected Papers / / edited by Giuseppe Persiano, Roberto Solis-Oba |
Edizione | [1st ed. 2005.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 |
Descrizione fisica | 1 online resource (VIII, 295 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Computer science - Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence - Data processing Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Online Packet Switching -- Approximation Algorithms for Mixed Fractional Packing and Covering Problems -- Regular Papers -- Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-Trees -- Online Bin Packing with Resource Augmentation -- A PTAS for Delay Minimization in Establishing Wireless Conference Calls -- This Side Up! -- Approximation Algorithm for Directed Multicuts -- Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria -- Approximation Algorithms for Spreading Points -- More Powerful and Simpler Cost-Sharing Methods -- Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints -- Priority Algorithms for Graph Optimization Problems -- Pricing Network Edges to Cross a River -- Submodular Integer Cover and Its Application to Production Planning -- Stochastic Online Scheduling on Parallel Machines -- A -Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path -- Order-Preserving Transformations and Greedy-Like Algorithms -- Off-line Admission Control for Advance Reservations in Star Networks -- Joint Base Station Scheduling -- Universal Bufferless Routing -- Strong Colorings of Hypergraphs -- Deterministic Monotone Algorithms for Scheduling on Related Machines -- Better Bounds for Minimizing SONET ADMs. |
Record Nr. | UNINA-9910767548803321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques [[electronic resource] ] : 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008 / / edited by Ashish Goel, Klaus Jansen, José Rolim, Ronitt Rubinfeld |
Edizione | [1st ed. 2008.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 |
Descrizione fisica | 1 online resource (XII, 604 p.) |
Disciplina | 004 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Computer programming
Computer science Algorithms Computer science—Mathematics Discrete mathematics Numerical analysis Programming Techniques Theory of Computation Discrete Mathematics in Computer Science Numerical Analysis |
ISBN | 3-540-85363-4 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Contributed Talks of APPROX -- Approximating Optimal Binary Decision Trees -- Santa Claus Meets Hypergraph Matchings -- Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction -- Connected Vertex Covers in Dense Graphs -- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies -- Sweeping Points -- Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness -- Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks -- Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP -- Approximating Maximum Subgraphs without Short Cycles -- Deterministic 7/8-Approximation for the Metric Maximum TSP -- Inapproximability of Survivable Networks -- Approximating Single Machine Scheduling with Scenarios -- Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity -- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One -- The Directed Minimum Latency Problem -- A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem -- Approximating Directed Weighted-Degree Constrained Networks -- A Constant Factor Approximation for Minimum ?-Edge-Connected k-Subgraph with Metric Costs -- Budgeted Allocations in the Full-Information Setting -- Contributed Talks of RANDOM -- Optimal Random Matchings on Trees and Applications -- Small Sample Spaces Cannot Fool Low Degree Polynomials -- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size -- Tensor Products of Weakly Smooth Codes Are Robust -- On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs -- Improved Bounds for Testing Juntas -- The Complexity of Distinguishing Markov Random Fields -- Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms -- Tight Bounds for Hashing Block Sources -- Improved Separations between Nondeterministic and Randomized Multiparty Communication -- Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs -- On the Query Complexity of Testing Orientations for Being Eulerian -- Approximately Counting Embeddings into Random Graphs -- Increasing the Output Length of Zero-Error Dispersers -- Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals -- The Complexity of Local List Decoding -- Limitations of Hardness vs. Randomness under Uniform Reductions -- Learning Random Monotone DNF -- Breaking the ?-Soundness Bound of the Linearity Test over GF(2) -- Dense Fast Random Projections and Lean Walsh Transforms -- Near Optimal Dimensionality Reductions That Preserve Volumes -- Sampling Hypersurfaces through Diffusion -- A 2-Source Almost-Extractor for Linear Entropy -- Extractors for Three Uneven-Length Sources -- The Power of Choice in a Generalized Pólya Urn Model -- Corruption and Recovery-Efficient Locally Decodable Codes -- Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets. |
Record Nr. | UNISA-996466075503316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques [[electronic resource] ] : 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008 / / edited by Ashish Goel, Klaus Jansen, José Rolim, Ronitt Rubinfeld |
Edizione | [1st ed. 2008.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 |
Descrizione fisica | 1 online resource (XII, 604 p.) |
Disciplina | 004 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Computer programming
Computer science Algorithms Computer science—Mathematics Discrete mathematics Numerical analysis Programming Techniques Theory of Computation Discrete Mathematics in Computer Science Numerical Analysis |
ISBN | 3-540-85363-4 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Contributed Talks of APPROX -- Approximating Optimal Binary Decision Trees -- Santa Claus Meets Hypergraph Matchings -- Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction -- Connected Vertex Covers in Dense Graphs -- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies -- Sweeping Points -- Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness -- Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks -- Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP -- Approximating Maximum Subgraphs without Short Cycles -- Deterministic 7/8-Approximation for the Metric Maximum TSP -- Inapproximability of Survivable Networks -- Approximating Single Machine Scheduling with Scenarios -- Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity -- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One -- The Directed Minimum Latency Problem -- A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem -- Approximating Directed Weighted-Degree Constrained Networks -- A Constant Factor Approximation for Minimum ?-Edge-Connected k-Subgraph with Metric Costs -- Budgeted Allocations in the Full-Information Setting -- Contributed Talks of RANDOM -- Optimal Random Matchings on Trees and Applications -- Small Sample Spaces Cannot Fool Low Degree Polynomials -- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size -- Tensor Products of Weakly Smooth Codes Are Robust -- On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs -- Improved Bounds for Testing Juntas -- The Complexity of Distinguishing Markov Random Fields -- Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms -- Tight Bounds for Hashing Block Sources -- Improved Separations between Nondeterministic and Randomized Multiparty Communication -- Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs -- On the Query Complexity of Testing Orientations for Being Eulerian -- Approximately Counting Embeddings into Random Graphs -- Increasing the Output Length of Zero-Error Dispersers -- Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals -- The Complexity of Local List Decoding -- Limitations of Hardness vs. Randomness under Uniform Reductions -- Learning Random Monotone DNF -- Breaking the ?-Soundness Bound of the Linearity Test over GF(2) -- Dense Fast Random Projections and Lean Walsh Transforms -- Near Optimal Dimensionality Reductions That Preserve Volumes -- Sampling Hypersurfaces through Diffusion -- A 2-Source Almost-Extractor for Linear Entropy -- Extractors for Three Uneven-Length Sources -- The Power of Choice in a Generalized Pólya Urn Model -- Corruption and Recovery-Efficient Locally Decodable Codes -- Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets. |
Record Nr. | UNINA-9910483381003321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques [[electronic resource] ] : 8th International Workshop on Approximation Algorithms for Compinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings / / edited by Chandra Chekuri, Klaus Jansen, José D.P. Rolim, Luca Trevisan |
Edizione | [1st ed. 2005.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 |
Descrizione fisica | 1 online resource (XI, 495 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Numerical analysis Computer science—Mathematics Discrete mathematics Numerical Analysis Discrete Mathematics in Computer Science |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Contributed Talks of APPROX -- The Network as a Storage Device: Dynamic Routing with Bounded Buffers -- Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT -- What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs -- A Rounding Algorithm for Approximating Minimum Manhattan Networks -- Packing Element-Disjoint Steiner Trees -- Approximating the Bandwidth of Caterpillars -- Where’s the Winner? Max-Finding and Sorting with Metric Costs -- What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization -- The Complexity of Making Unique Choices: Approximating 1-in-k SAT -- Approximating the Distortion -- Approximating the Best-Fit Tree Under L p Norms -- Beating a Random Assignment -- Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints -- Approximation Algorithms for Network Design and Facility Location with Service Capacities -- Finding Graph Matchings in Data Streams -- A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses -- Efficient Approximation of Convex Recolorings -- Approximation Algorithms for Requirement Cut on Graphs -- Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems -- Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy -- Contributed Talks of RANDOM -- Bounds for Error Reduction with Few Quantum Queries -- Sampling Bounds for Stochastic Optimization -- An Improved Analysis of Mergers -- Finding a Maximum Independent Set in a Sparse Random Graph -- On the Error Parameter of Dispersers -- Tolerant Locally Testable Codes -- A Lower Bound on List Size for List Decoding -- A Lower Bound for Distribution-Free Monotonicity Testing -- On Learning Random DNF Formulas Under the Uniform Distribution -- Derandomized Constructions of k-Wise (Almost) Independent Permutations -- Testing Periodicity -- The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem -- The Online Clique Avoidance Game on Random Graphs -- A Generating Function Method for the Average-Case Analysis of DPLL -- A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas -- Mixing Points on a Circle -- Derandomized Squaring of Graphs -- Tight Bounds for String Reconstruction Using Substring Queries -- Reconstructive Dispersers and Hitting Set Generators -- The Tensor Product of Two Codes Is Not Necessarily Robustly Testable -- Fractional Decompositions of Dense Hypergraphs. |
Record Nr. | UNISA-996465925803316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques [[electronic resource] ] : 8th International Workshop on Approximation Algorithms for Compinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings / / edited by Chandra Chekuri, Klaus Jansen, José D.P. Rolim, Luca Trevisan |
Edizione | [1st ed. 2005.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 |
Descrizione fisica | 1 online resource (XI, 495 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Numerical analysis Computer science—Mathematics Discrete mathematics Numerical Analysis Discrete Mathematics in Computer Science |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Contributed Talks of APPROX -- The Network as a Storage Device: Dynamic Routing with Bounded Buffers -- Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT -- What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs -- A Rounding Algorithm for Approximating Minimum Manhattan Networks -- Packing Element-Disjoint Steiner Trees -- Approximating the Bandwidth of Caterpillars -- Where’s the Winner? Max-Finding and Sorting with Metric Costs -- What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization -- The Complexity of Making Unique Choices: Approximating 1-in-k SAT -- Approximating the Distortion -- Approximating the Best-Fit Tree Under L p Norms -- Beating a Random Assignment -- Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints -- Approximation Algorithms for Network Design and Facility Location with Service Capacities -- Finding Graph Matchings in Data Streams -- A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses -- Efficient Approximation of Convex Recolorings -- Approximation Algorithms for Requirement Cut on Graphs -- Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems -- Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy -- Contributed Talks of RANDOM -- Bounds for Error Reduction with Few Quantum Queries -- Sampling Bounds for Stochastic Optimization -- An Improved Analysis of Mergers -- Finding a Maximum Independent Set in a Sparse Random Graph -- On the Error Parameter of Dispersers -- Tolerant Locally Testable Codes -- A Lower Bound on List Size for List Decoding -- A Lower Bound for Distribution-Free Monotonicity Testing -- On Learning Random DNF Formulas Under the Uniform Distribution -- Derandomized Constructions of k-Wise (Almost) Independent Permutations -- Testing Periodicity -- The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem -- The Online Clique Avoidance Game on Random Graphs -- A Generating Function Method for the Average-Case Analysis of DPLL -- A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas -- Mixing Points on a Circle -- Derandomized Squaring of Graphs -- Tight Bounds for String Reconstruction Using Substring Queries -- Reconstructive Dispersers and Hitting Set Generators -- The Tensor Product of Two Codes Is Not Necessarily Robustly Testable -- Fractional Decompositions of Dense Hypergraphs. |
Record Nr. | UNINA-9910483161103321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques [[electronic resource] ] : 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA,USA, August 18-20, 2001 / / edited by Michel Goemans, Klaus Jansen, Jose D.P. Rolim, Luca Trevisan |
Edizione | [1st ed. 2001.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2001 |
Descrizione fisica | 1 online resource (IX, 296 p.) |
Disciplina | 004/.01/5114 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Mathematical analysis
Analysis (Mathematics) Computer programming Discrete mathematics Algorithms Numerical analysis Combinatorics Analysis Programming Techniques Discrete Mathematics Algorithm Analysis and Problem Complexity Numeric Computing |
ISBN | 3-540-44666-4 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Using Complex Semidefinite Programming for Approximating MAX E2-LIN3 -- Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems -- Web Search via Hub Synthesis -- Error-Correcting Codes and Pseudorandom Projections -- Order in Pseudorandomness -- Contributed Talks of APPROX -- Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows -- On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique -- Online Weighted Flow Time and Deadline Scheduling -- An Online Algorithm for the Postman Problem with a Small Penalty -- A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem -- Approximation Schemes for Ordered Vector Packing Problems -- Incremental Codes -- A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set -- Approximation Algorithms for Budget-Constrained Auctions -- Minimizing Average Completion of Dedicated Tasks and Interval Graphs -- A Greedy Facility Location Algorithm Analyzed Using Dual Fitting -- 0.863-Approximation Algorithm for MAX DICUT -- The Maximum Acyclic Subgraph Problem and Degree-3 Graphs -- Some Approximation Results for the Maximum Agreement Forest Problem -- Contributed Talks of RANDOM -- Near-optimum Universal Graphs for Graphs with Bounded Degrees -- On a Generalized Ruin Problem -- On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation -- Exact Sampling in Machine Scheduling Problems -- On Computing Ad-hoc Selective Families -- L Infinity Embeddings -- On Euclidean Embeddings and Bandwidth Minimization -- The Non-approximability of Non-Boolean Predicates -- On the Derandomization of Constant Depth Circuits -- Testing Parenthesis Languages -- Proclaiming Dictators and Juntas or Testing Boolean Formulae -- Equitable Coloring Extends Chernoff-Hoeffding Bounds. |
Record Nr. | UNINA-9910143591803321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2001 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques [[electronic resource] ] : 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA,USA, August 18-20, 2001 / / edited by Michel Goemans, Klaus Jansen, Jose D.P. Rolim, Luca Trevisan |
Edizione | [1st ed. 2001.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2001 |
Descrizione fisica | 1 online resource (IX, 296 p.) |
Disciplina | 004/.01/5114 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Mathematical analysis
Analysis (Mathematics) Computer programming Discrete mathematics Algorithms Numerical analysis Combinatorics Analysis Programming Techniques Discrete Mathematics Algorithm Analysis and Problem Complexity Numeric Computing |
ISBN | 3-540-44666-4 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Using Complex Semidefinite Programming for Approximating MAX E2-LIN3 -- Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems -- Web Search via Hub Synthesis -- Error-Correcting Codes and Pseudorandom Projections -- Order in Pseudorandomness -- Contributed Talks of APPROX -- Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows -- On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique -- Online Weighted Flow Time and Deadline Scheduling -- An Online Algorithm for the Postman Problem with a Small Penalty -- A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem -- Approximation Schemes for Ordered Vector Packing Problems -- Incremental Codes -- A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set -- Approximation Algorithms for Budget-Constrained Auctions -- Minimizing Average Completion of Dedicated Tasks and Interval Graphs -- A Greedy Facility Location Algorithm Analyzed Using Dual Fitting -- 0.863-Approximation Algorithm for MAX DICUT -- The Maximum Acyclic Subgraph Problem and Degree-3 Graphs -- Some Approximation Results for the Maximum Agreement Forest Problem -- Contributed Talks of RANDOM -- Near-optimum Universal Graphs for Graphs with Bounded Degrees -- On a Generalized Ruin Problem -- On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation -- Exact Sampling in Machine Scheduling Problems -- On Computing Ad-hoc Selective Families -- L Infinity Embeddings -- On Euclidean Embeddings and Bandwidth Minimization -- The Non-approximability of Non-Boolean Predicates -- On the Derandomization of Constant Depth Circuits -- Testing Parenthesis Languages -- Proclaiming Dictators and Juntas or Testing Boolean Formulae -- Equitable Coloring Extends Chernoff-Hoeffding Bounds. |
Record Nr. | UNISA-996465806303316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2001 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|