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