Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006. Proceedings

Johan Håstad (auth.), Josep Díaz, Klaus Jansen, José D. P. Rolim, Uri Zwick (eds.)3540380442, 9783540380443

This book constitutes the joint refereed proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and the 10th International Workshop on Randomization and Computation, RANDOM 2006, held in Barcelona, Spain, in August 2006.

The 44 revised full papers presented were carefully reviewed and selected from 105 submissions. Among the topics covered are design and analysis of approximation algorithms, hardness of approximation problems, small spaces and data streaming algorithms, sub-linear time algorithms, embeddings and metric space methods, mathematical programming methods, coloring and partitioning, cuts and connectivity, game theory, network design and routing, packing and covering, scheduling, design and analysis of randomized algorithms, randomized complexity theory, pseudorandomness, derandomization, random combinatorial structures, Markov chains, prohabalistic proof systems, error-correcting codes, etc.

 

---

Table of contents :
Front Matter….Pages –
On Nontrivial Approximation of CSPs….Pages 1-1
Analysis of Algorithms on the Cores of Random Graphs….Pages 2-2
Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs….Pages 3-14
Approximating Precedence-Constrained Single Machine Scheduling by Coloring….Pages 15-26
Minimizing Setup and Beam-On Times in Radiation Therapy….Pages 27-38
On the Value of Preemption in Scheduling….Pages 39-48
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs….Pages 49-60
Tight Results on Minimum Entropy Set Cover….Pages 61-69
A Tight Lower Bound for the Steiner Point Removal Problem on Trees….Pages 70-81
Single-Source Stochastic Routing….Pages 82-94
An O (log n ) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem….Pages 95-103
Online Algorithms to Minimize Resource Reallocations and Network Communication….Pages 104-115
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs….Pages 116-127
Combinatorial Algorithms for Data Migration to Minimize Average Completion Time….Pages 128-139
LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times….Pages 140-151
Approximating Buy-at-Bulk and Shallow-Light k -Steiner Trees….Pages 152-163
Improved Algorithms for Data Migration….Pages 164-175
Approximation Algorithms for Graph Homomorphism Problems….Pages 176-187
Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem….Pages 188-199
Hardness of Preemptive Finite Capacity Dial-a-Ride….Pages 200-211
Minimum Vehicle Routing with a Common Deadline….Pages 212-223
Stochastic Combinatorial Optimization with Controllable Risk Aversion Level….Pages 224-235
Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems….Pages 236-247
Better Approximations for the Minimum Common Integer Partition Problem….Pages 248-259
On Pseudorandom Generators with Linear Stretch in NC 0  ….Pages 260-271
A Fast Random Sampling Algorithm for Sparsifying Matrices….Pages 272-279
The Effect of Boundary Conditions on Mixing Rates of Markov Chains….Pages 280-291
Adaptive Sampling and Fast Low-Rank Matrix Approximation….Pages 292-303
Robust Local Testability of Tensor Products of LDPC Codes….Pages 304-315
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods….Pages 316-326
Dobrushin Conditions and Systematic Scan….Pages 327-338
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems….Pages 339-350
Robust Mixing….Pages 351-362
Approximating Average Parameters of Graphs….Pages 363-374
Local Decoding and Testing for Homomorphisms….Pages 375-385
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy….Pages 386-397
Randomness-Efficient Sampling Within NC 1 ….Pages 398-409
Monotone Circuits for the Majority Function….Pages 410-425
Space Complexity vs. Query Complexity….Pages 426-437
Consistency of Local Density Matrices Is QMA-Complete….Pages 438-449
On Bounded Distance Decoding for General Lattices….Pages 450-461
Threshold Functions for Asymmetric Ramsey Properties Involving Cliques….Pages 462-474
Distance Approximation in Bounded-Degree and General Sparse Graphs….Pages 475-486
Fractional Matching Via Balls-and-Bins….Pages 487-498
A Randomized Solver for Linear Systems with Exponential Convergence….Pages 499-507
Maintaining External Memory Efficient Hash Tables….Pages 508-519
Back Matter….Pages –