List of accepted papers for APPROX 2011:


Michael Crouch and Andrew Mcgregor. 
Periodicity and Cyclic Shifts via Linear Sketches

Adrian Dumitrescu, Minghui Jiang and Janos Pach. 
Opaque sets

Nachshon Cohen and Zeev Nutov. 
A $(1+\ln 2)$-approximation algorithm for minimum-cost $2$-edge-connectivity augmentation of trees with constant radius

Yair Bartal, Douglas Carroll, Adam Meyerson and Ofer Neiman. 
Bandwidth and Low Dimensional Embedding

Timothy Carnes and David Shmoys. 
Primal-Dual Schema and Lagrangian Relaxation for the k-Location Routing Problem

Sanjeev Arora and Rong Ge. 
New Tools for Graph Coloring

Johan Hastad. 
Satisfying degree d equations over GF[2]^n

Sagi Snir and Raphael Yuster. 
A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs

Sandor Fekete, Tom Kamphans, Alexander Kroeller, Joseph Mitchell and Christiane Schmidt. 
Exploring and Triangulating a Region by a Swarm of Robots

Venkatesan Chakaravarthy, Amit Kumar, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal. 
Scheduling Resources for Throughput Maximization

Michael Kapralov and Rina Panigrahy. 
Multiplicative approximations of random walk transition probabilities

Maurice Cheung and David Shmoys. 
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

M. Reza Khani and Mohammad Salavatipour. 
Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems

Feodor Dragan and Ekkehard Koehler. 
An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs

Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. 
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs

Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. 
Social Welfare in One-sided Matching Markets without Money

Rohit Khandekar, Guy Kortsarz and Zeev Nutov. 
Approximating node-connectivity and prize-collecting network-design problems with degree constraints

Chandan Dubey and Thomas Holenstein. 
Approximating lattice problems using an approximate shortest vector oracle

Moran Feldman, Seffi Naor and Roy Schwartz. 
Improved Competitive Ratios for Submodular Secretary Problems

Inge Li Gortz and Viswanath Nagarajan. 
Locating Depots for Capacitated Vehicle Routing

Parinya Chalermsook. 
Coloring and Maximum Independent Set of Rectangles

Piotr Berman, Erik D. Demaine and Morteza Zadimoghaddam. 
O(1)-Approximations for Maximum Movement Problems

Zhiyi Huang, Lei Wang and Yuan Zhou. 
Black-Box Reductions in Mechanism Design

Sushant Sachdeva and Rishi Saket. 
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs

Per Austrin, Mark Braverman and Eden Chlamtac. 
Inapproximability of NP-Complete Variants of Nash Equilibrium

Marek Karpinski and Warren Schudy. 
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems

Nikhil Bansal, Ravishankar Krishnaswamy and Barna Saha. 
On Capacitated Set Cover Problems

Anand Louis, Prasad Raghavendra, Prasad Tetali and Santosh Vempala. 
Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions

Khanh Do Ba and Piotr Indyk. 
Sparse recovery with partial support knowledge