List of accepted papers for APPROX 2007:


Maximum gradient embeddings and monotone clustering
Manor Mendel and Assaf Naor

On the approximation resistance of a random predicate
Johan Hastad

Almost exact matchings
Raphael Yuster

Parity and contraction in planar graph embeddings
Amit Chakrabarti, James Lee and Justin Vincent

Coarse differentiation and multi-flows in planar graphs
James Lee and Prasad Raghavendra

An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
Jaroslaw Byrka

Packing and covering delta-hyperbolic spaces by balls
Victor Chepoi and Bertrand Estellon

Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows
Greg Frederickson and Barry Wittman

Approximation algorithms and hardness for domination with propagation
Ashkan Aazami and Michael Stilp

Stochastic Steiner Tree with Non-Uniform Inflation
Anupam Gupta, MohammadTaghi Hajiaghayi and Amit Kumar

Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems
Viswanath Nagarajan and R Ravi

Soft Edge Coloring
Chadi Kari, Yoo-Ah Kim, Seungjoon Lee, Alexander Russell and Min-ho Shin

Increasing the Span of Stars
Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra and Gyanit Singh

Improved approximation ratios for traveling salesperson tours and paths in directed graphs
Uriel Feige and Mohit Singh

Two Randomized Mechanisms for Combinatorial Auctions
Shahar Dobzinski

Hardness of Embedding Metric Spaces of Equal Size
Subhash Khot and Rishi Saket

Optimal Resource Augmentations for Online Knapsack
Kazuo Iwama and Guochuan Zhang

Approximation Algorithms for the Max-Min Allocation problem
Ashok Kumar Ponnuswami and Subhash Khot

Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of negative type metrics
Hamed Hatami, Avner Magen and Evangelos Markakis

Encouraging Cooperation in Sharing Supermodular Costs
Andreas S. Schulz and Nelson Uhan

Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems
Ilias Diakonikolas and Mihalis Yannakakis

A Knapsack Secretary Problem with Applications
Moshe Babaioff, Nicole Immorlica, David Kempe and Robert Kleinberg