Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques: 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Proble Book

Invited Talks
On Nontrivial Approximation of CSPs   Johan Hastad     1
Analysis of Algorithms on the Cores of Random Graphs   Nick Wormald     2
Contributed Talks of APPROX
Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs   Christoph Ambuhl   Thomas Erlebach   Matus Mihal'ak   Marc Nunkesser     3
Approximating Precedence-Constrained Single Machine Scheduling by Coloring   Christoph Ambuhl   Monaldo Mastrolilli   Ola Svensson     15
Minimizing Setup and Beam-On Times in Radiation Therapy   Nikhil Bansal   Don Coppersmith   Baruch Schieber     27
On the Value of Preemption in Scheduling   Yair Bartal   Stefano Leonardi   Gil Shallom   Rene Sitters     39
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs   Benjamin E. Birnbaum   Kenneth J. Goldman     49
Tight Results on Minimum Entropy Set Cover   Jean Cardinal   Samuel Fiorini   Gwenael Joret     61
A Tight Lower Bound for the Steiner Point Removal Problem on Trees. T.-H.   Hubert Chan   Donglin Xia   Goran Konjevod   Andrea Richa     70
Single-Source Stochastic Routing   Shuchi Chawla   Tim Roughgarden     82
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem   Chandra Chekuri   Martin Pal     95
Online Algorithms to Minimize Resource Reallocations and Network Communication   Sashka Davis   Jeff Edmonds   Russell Impagliazzo     104
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs   Leah Epstein   Magnus M. Halldorsson   Asaf Levin   Hadas Shachnai     116
Combinatorial Algorithms for Data Migration to Minimize Average Completion Time   Rajiv Gandhi   Julian Mestre     128
LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times   Alexander Grigoriev   Maxim Sviridenko   Marc Uetz     140
Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees   Mohammad Taghi Hajiaghayi   Guy Kortsarz   Mohammad R. Salavatipour     152
Improved Algorithms for Data Migration   Samir Khuller   Yoo-Ah Kim   Azarakhsh Malekian     164
Approximation Algorithms for Graph Homomorphism Problems   Michael Langberg   Yuval Rabani   Chaitanya Swamy      176
Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem   Retsef Levi   Maxim Sviridenko     188
Hardness of Preemptive Finite Capacity Dial-a-Ride Inge Li Gortz     200
Minimum Vehicle Routing with a Common Deadline   Viswanath Nagarajan   R. Ravi     212
Stochastic Combinatorial Optimization with Controllable Risk Aversion Level   Anthony Man-Cho So   Jiawei Zhang   Yinyu Ye     224
Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems Zeev Nutov     236
Better Approximations for the Minimum Common Integer Partition Problem David P. Woodruff     248
Contributed Talks of Random
On Pseudorandom Generators with Linear Stretch in NC[superscript 0]   Benny Applebaum   Yuval Ishai   Eyal Kushilevitz     260
A Fast Random Sampling Algorithm for Sparsifying Matrices   Sanjeev Arora   Elad Hazan   Satyen Kale     272
The Effect of Boundary Conditions on Mixing Rates of Markov Chains   Nayantara Bhatnagar   Sam Greenberg   Dana Randall     280
Adaptive Sampling and Fast Low-Rank Matrix Approximation   Amit Deshpande   Santosh Vempala     292
Robust Local Testability of Tensor Products of LDPC Codes   Irit Dinur   Madhu Sudan   Avi Wigderson     304
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods   Petros Drineas   Michael W. Mahoney   S. Muthukrishnan     316
Dobrushin Conditions and Systematic Scan   Martin Dyer   Leslie Ann Goldberg   Mark Jerrum     327
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems   Uriel Feige   Elchanan Mossel   Dan Vilenchik     339
Robust Mixing Murali K. Ganapathy     351
Approximating Average Parameters of Graphs   Oded Goldreich   Dana Ron     363
Local Decoding and Testing for Homomorphisms   Elena Grigorescu   Swastik Kopparty   Madhu Sudan     375
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy Dan Gutfreund     386
Randomness-Efficient Sampling Within NC[superscript 1] Alexander Healy     398
Monotone Circuits for the Majority Function   Shlomo Hoory   Avner Magen   Toniann Pitassi     410
Space Complexity vs. Query Complexity   Oded Lachish   Ilan Newman   Asaf Shapira     426
Consistency of Local Density Matrices Is QMA-Complete Yi-Kai Liu     438
On Bounded Distance Decoding for General Lattices   Yi-Kai Liu   Vadim Lyubashevsky   Daniele Micciancio     450
Threshold Functions for Asymmetric Ramsey Properties Involving Cliques   Martin Marciniszyn   Jozef Skokan   Reto Spohel   Angelika Steger     462
Distance Approximation in Bounded-Degree and General Sparse Graphs   Sharon Marko   Dana Ron     475
Fractional Matching Via Balls-and-Bins   Rajeev Motwani   Rina Panigrahy   Ying Xu     487
A Randomized Solver for Linear Systems with Exponential Convergence   Thomas Strohmer   Roman Vershynin     499
Maintaining External Memory Efficient Hash Tables   Philipp Woelfel     508
Author Index     521