This book constitutes the joint refereed proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009, and the 13th International Workshop on Randomization and Computation, RANDOM 2009, held in Berkeley, CA, USA, in August 2009.
The 25 revised full papers of the APPROX 2009 workshop and the 28 revised full papers of the RANDOM 2009 workshop included in this volume, were carefully reviewed and selected from 56 and 58 submissions, respectively. APPROX focuses on algorithmic and complexity issues surrounding the development of efficient approximate solutions to computationally difficult problems. RANDOM is concerned with applications of randomness to computational and combinatorial problems.
Author(s): Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani (auth.), Irit Dinur, Klaus Jansen, Joseph Naor, José Rolim (eds.)
Series: Lecture Notes in Computer Science 5687 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 742
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Symbolic and Algebraic Manipulation; Probability and Statistics in Computer Science; Coding and Information Theory
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 -
