Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques: 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings

Micah Adler, Brent Heeringa (auth.), Ashish Goel, Klaus Jansen, José D. P. Rolim, Ronitt Rubinfeld (eds.)3540853626, 9783540853626

This book constitutes the joint refereed proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and the 12th International Workshop on Randomization and Computation, RANDOM 2008, held in Boston, MA, USA, in August 2008.

The 20 revised full papers of the APPROX 2008 workshop were carefully reviewed and selected from 42 submissions and focus on algorithmic and complexity issues surrounding the development of efficient approximate solutions to computationally difficult problems. RANDOM 2008 is concerned with applications of randomness to computational and combinatorial problems and accounts for 27 revised full papers, also diligently reviewed and selected out of 52 workshop submissions.

Table of contents :
Front Matter….Pages –
Approximating Optimal Binary Decision Trees….Pages 1-9
Santa Claus Meets Hypergraph Matchings….Pages 10-20
Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction….Pages 21-34
Connected Vertex Covers in Dense Graphs….Pages 35-48
Improved Approximation Guarantees through Higher Levels of SDP Hierarchies….Pages 49-62
Sweeping Points….Pages 63-76
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness….Pages 77-90
Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks….Pages 91-103
Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP….Pages 104-117
Approximating Maximum Subgraphs without Short Cycles….Pages 118-131
Deterministic 7/8-Approximation for the Metric Maximum TSP….Pages 132-145
Inapproximability of Survivable Networks….Pages 146-152
Approximating Single Machine Scheduling with Scenarios….Pages 153-164
Streaming Algorithms for k -Center Clustering with Outliers and with Anonymity….Pages 165-178
A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One….Pages 179-192
The Directed Minimum Latency Problem….Pages 193-206
A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem….Pages 207-218
Approximating Directed Weighted-Degree Constrained Networks….Pages 219-232
A Constant Factor Approximation for Minimum λ -Edge-Connected k -Subgraph with Metric Costs….Pages 233-246
Budgeted Allocations in the Full-Information Setting….Pages 247-253
Optimal Random Matchings on Trees and Applications….Pages 254-265
Small Sample Spaces Cannot Fool Low Degree Polynomials….Pages 266-275
Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size….Pages 276-289
Tensor Products of Weakly Smooth Codes Are Robust….Pages 290-302
On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs….Pages 303-316
Improved Bounds for Testing Juntas….Pages 317-330
The Complexity of Distinguishing Markov Random Fields….Pages 331-342
Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms….Pages 343-356
Tight Bounds for Hashing Block Sources….Pages 357-370
Improved Separations between Nondeterministic and Randomized Multiparty Communication….Pages 371-384
Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs….Pages 385-401
On the Query Complexity of Testing Orientations for Being Eulerian….Pages 402-415
Approximately Counting Embeddings into Random Graphs….Pages 416-429
Increasing the Output Length of Zero-Error Dispersers….Pages 430-443
Euclidean Sections of $ell_1^N$ with Sublinear Randomness and Error-Correction over the Reals….Pages 444-454
The Complexity of Local List Decoding….Pages 455-468
Limitations of Hardness vs. Randomness under Uniform Reductions….Pages 469-482
Learning Random Monotone DNF….Pages 483-497
Breaking the ε -Soundness Bound of the Linearity Test over GF(2)….Pages 498-511
Dense Fast Random Projections and Lean Walsh Transforms….Pages 512-522
Near Optimal Dimensionality Reductions That Preserve Volumes….Pages 523-534
Sampling Hypersurfaces through Diffusion….Pages 535-548
A 2-Source Almost-Extractor for Linear Entropy….Pages 549-556
Extractors for Three Uneven-Length Sources….Pages 557-570
The Power of Choice in a Generalized Pólya Urn Model….Pages 571-583
Corruption and Recovery-Efficient Locally Decodable Codes….Pages 584-595
Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets….Pages 596-601
Back Matter….Pages –