Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings

Front Matter....Pages -
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs....Pages 1-14
Adaptive Sampling for k -Means Clustering....Pages 15-28
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs....Pages 29-41
Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs....Pages 42-55
Truthful Mechanisms via Greedy Iterative Packing....Pages 56-69
Resource Minimization Job Scheduling....Pages 70-83
The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders....Pages 84-97
New Hardness Results for Diophantine Approximation....Pages 98-110
PASS Approximation....Pages 111-124
Optimal Sherali-Adams Gaps from Pairwise Independence....Pages 125-139
An Approximation Scheme for Terrain Guarding....Pages 140-148
Scheduling with Outliers....Pages 149-162
Improved Inapproximability Results for Maximum k -Colorable Subgraph....Pages 163-176
Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems....Pages 177-189
On the Optimality of Gluing over Scales....Pages 190-201
On Hardness of Pricing Items for Single-Minded Bidders....Pages 202-216
Real-Time Message Routing and Scheduling....Pages 217-230
Approximating Some Network Design Problems with Node Costs....Pages 231-243
Submodular Maximization over Multiple Matroids via Generalized Exchange Properties....Pages 244-257
Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy....Pages 258-271
Minimizing Average Shortest Path Distances via Shortcut Edge Addition....Pages 272-285
Approximating Node-Connectivity Augmentation Problems....Pages 286-297
A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem....Pages 298-311
Approximation Algorithms for Domatic Partitions of Unit Disk Graphs....Pages 312-325
On the Complexity of the Asymmetric VPN Problem....Pages 326-338
Deterministic Approximation Algorithms for the Nearest Codeword Problem....Pages 339-351
Strong Parallel Repetition Theorem for Free Projection Games....Pages 352-365
Random Low Degree Polynomials are Hard to Approximate....Pages 366-377
Composition of Semi-LTCs by Two-Wise Tensor Products....Pages 378-391
On the Security of Goldreich’s One-Way Function....Pages 392-405
Random Tensors and Planted Cliques....Pages 406-419
Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry....Pages 420-433
Average-Case Analyses of Vickrey Costs....Pages 434-447
A Hypergraph Dictatorship Test with Perfect Completeness....Pages 448-461
Extractors Using Hardness Amplification....Pages 462-475
How Well Do Random Walks Parallelize?....Pages 476-489
An Analysis of Random-Walk Cuckoo Hashing....Pages 490-503
Hierarchy Theorems for Property Testing....Pages 504-519
Algorithmic Aspects of Property Testing in the Dense Graphs Model....Pages 520-533
Succinct Representation of Codes with Applications to Testing....Pages 534-547
Efficient Quantum Tensor Product Expanders and k -Designs....Pages 548-561
Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND....Pages 562-573
Pseudorandom Generators and Typically-Correct Derandomization....Pages 574-587
Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions....Pages 588-600
Tolerant Linearity Testing and Locally Testable Codes....Pages 601-614
Pseudorandom Bit Generators That Fool Modular Sums....Pages 615-630
The Glauber Dynamics for Colourings of Bounded Degree Trees....Pages 631-645
Testing ±1-weight halfspace....Pages 646-657
Small-Bias Spaces for Group Products....Pages 658-672
Small Clique Detection and Approximate Nash Equilibria....Pages 673-685
Testing Computability by Width Two OBDDs....Pages 686-699
Improved Polynomial Identity Testing for Read-Once Formulas....Pages 700-713
Smooth Analysis of the Condition Number and the Least Singular Value....Pages 714-737
Erratum: Resource Minimization Job Scheduling....Pages E1-E1
Back Matter....Pages -