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

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 -