Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Invited Talks.- On Nontrivial Approximation of CSPs.- Analysis of Algorithms on the Cores of Random Graphs.- Contributed Talks of APPROX.- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs.- Approximating Precedence-Constrained Single Machine Scheduling by Coloring.- Minimizing Setup and Beam-On Times in Radiation Therapy.- On the Value of Preemption in Scheduling.- An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs.- Tight Results on Minimum Entropy Set Cover.- A Tight Lower Bound for the Steiner Point Removal Problem on Trees.- Single-Source Stochastic Routing.- An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem.- Online Algorithms to Minimize Resource Reallocations and Network Communication.- Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.- Combinatorial Algorithms for Data Migration to Minimize Average Completion Time.- LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times.- Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees.- Improved Algorithms for Data Migration.- Approximation Algorithms for Graph Homomorphism Problems.- Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem.- Hardness of Preemptive Finite Capacity Dial-a-Ride.- Minimum Vehicle Routing with a Common Deadline.- Stochastic Combinatorial Optimization with Controllable Risk Aversion Level.- Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems.- Better Approximations for the Minimum Common Integer Partition Problem.- Contributed Talks of RANDOM.- On Pseudorandom Generators with Linear Stretch in NC0.- A Fast Random Sampling Algorithm for Sparsifying Matrices.- The Effect of Boundary Conditions on Mixing Rates of Markov Chains.- Adaptive Sampling and Fast Low-Rank Matrix Approximation.- Robust Local Testability of Tensor Products of LDPC Codes.- Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods.- Dobrushin Conditions and Systematic Scan.- Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.- Robust Mixing.- Approximating Average Parameters of Graphs.- Local Decoding and Testing for Homomorphisms.- Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy.- Randomness-Efficient Sampling Within NC 1.- Monotone Circuits for the Majority Function.- Space Complexity vs. Query Complexity.- Consistency of Local Density Matrices Is QMA-Complete.- On Bounded Distance Decoding for General Lattices.- Threshold Functions for Asymmetric Ramsey Properties Involving Cliques.- Distance Approximation in Bounded-Degree and General Sparse Graphs.- Fractional Matching Via Balls-and-Bins.- A Randomized Solver for Linear Systems with Exponential Convergence.- Maintaining External Memory Efficient Hash Tables.