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

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 -