Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007. Proceedings

Ashkan Aazami, Michael D. Stilp (auth.), Moses Charikar, Klaus Jansen, Omer Reingold, José D. P. Rolim (eds.)3540742077, 9783540742074

This volume contains the papers presented at the 10th International Workshopon Approximation Algorithms for Combinatorial Optimization Problems(APPROX 2007) and the 11th International Workshop on Randomization andComputation (RANDOM 2007), which took place concurrently at PrincetonUniversity, on August 20–22, 2007. APPROX focuses on algorithmic and complexityissues surrounding the development of efficient approximate solutionsto computationally difficult problems.

---

Table of contents :
Front Matter….Pages –
Approximation Algorithms and Hardness for Domination with Propagation….Pages 1-15
A Knapsack Secretary Problem with Applications….Pages 16-28
An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem….Pages 29-43
Improved Approximation Algorithms for the Spanning Star Forest Problem….Pages 44-58
Packing and Covering δ -Hyperbolic Spaces by Balls….Pages 59-73
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems….Pages 74-88
Two Randomized Mechanisms for Combinatorial Auctions….Pages 89-103
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs….Pages 104-118
Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows….Pages 119-133
Stochastic Steiner Tree with Non-uniform Inflation….Pages 134-148
On the Approximation Resistance of a Random Predicate….Pages 149-163
Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ℓ 1 Embeddability of Negative Type Metrics….Pages 164-179
Optimal Resource Augmentations for Online Knapsack….Pages 180-188
Soft Edge Coloring….Pages 189-203
Approximation Algorithms for the Max-Min Allocation Problem….Pages 204-217
Hardness of Embedding Metric Spaces of Equal Size….Pages 218-227
Coarse Differentiation and Multi-flows in Planar Graphs….Pages 228-241
Maximum Gradient Embeddings and Monotone Clustering….Pages 242-256
Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems….Pages 257-270
Encouraging Cooperation in Sharing Supermodular Costs….Pages 271-285
Almost Exact Matchings….Pages 286-295
On Approximating the Average Distance Between Points….Pages 296-310
On Locally Decodable Codes, Self-correctable Codes, and t -Private PIR….Pages 311-325
A Sequential Algorithm for Generating Random Graphs….Pages 326-340
Local Limit Theorems for the Giant Component of Random Hypergraphs….Pages 341-352
Derandomization of Euclidean Random Walks….Pages 353-365
High Entropy Random Selection Protocols….Pages 366-379
Testing st -Connectivity….Pages 380-394
Properly 2-Colouring Linear Hypergraphs….Pages 395-408
Random Subsets of the Interval and P2P Protocols….Pages 409-421
The Cover Time of Random Digraphs….Pages 422-435
Eigenvectors of Random Graphs: Nodal Domains….Pages 436-448
Lower Bounds for Swapping Arthur and Merlin….Pages 449-463
Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects….Pages 464-478
On Estimating Frequency Moments of Data Streams….Pages 479-493
Distribution-Free Testing Lower Bounds for Basic Boolean Functions….Pages 494-508
On the Randomness Complexity of Property Testing….Pages 509-524
On the Benefits of Adaptivity in Property Testing of Dense Graphs….Pages 525-539
Slow Mixing of Markov Chains Using Fault Lines and Fat Contours….Pages 540-553
Better Binary List-Decodable Codes Via Multilevel Concatenation….Pages 554-568
Worst-Case to Average-Case Reductions Revisited….Pages 569-583
On Finding Frequent Elements in a Data Stream….Pages 584-595
Implementing Huge Sparse Random Graphs….Pages 596-608
Sublinear Algorithms for Approximating String Compressibility….Pages 609-623
Back Matter….Pages –