List of accepted papers for APPROX 2005:


Approximation Algorithms for Requirement cut on Graphs
Viswanath Nagarajan and R. Ravi

Beating a random assignment
Gustav Hast

Packing Element-Disjoint Steiner Trees
Joseph Cheriyan and Mohammad R. Salavatipour

Approximating the Distotrion
Alexander Hall and Christos Papadimitriou

A rounding algorithm for approximating minimum Manhattan networks
Victor Chepoi and Karim Nouioua and Yann Vaxes

Approximation Algorithms for Network Design and Facility Location with Service Capacities
Jens Massberg and Jens Vygen

Where's the Winner ? (Max-finding and Sorting with Metric Comparison Costs)
Anupam Gupta and Amit Kumar

Approximating the Best-Fit Tree under $L_p$ Norms
Boulos Harb and Sampath Kannan and Andrew McGregor

Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovasz-Schrijver Hierarchy
Iannis Tourlakis

Approximation Schemes for Node-Weighted Geometric Steiner Tree
Jan Remy and Angelika Steger

A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses
Julian Mestre

The Complexity of Making Unique Choices: Approximating 1-in-k SAT
Venkatesan Guruswami and Luca Trevisan

Finding Matchings in the Streaming Model
Andrew McGregor

What about Wednesday? Approximation Algorithms for Multistage Stochastic Optimization
Anupam Gupta and Martin Pal and R. Ravi and Amitabh Sinha

Approximation Algorithms for Scheduling on Unrelated Machines under Tree-Like Precedence Constraints
V. S. Anil Kumar and Madhav V. Marathe and Srinivasan Parthasarathy and Aravind Srinivasan

What would Edmonds do?  Augmenting paths and witnesses for degree-bounded MSTs
Kamalika Chaudhuri and Satish Rao and Samantha Riesenfeld and Kunal Talwar

The Network as a Storage Device: Dynamic Routing with Bounded Buffers
Stanislav Angelov and Sanjeev Khanna and Keshav Kunal

Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT
Adi Avidor and Uri Zwick

Efficient Approximation of Convex Recolorings
Shlomo Moran and Sagi Snir

Caterpillar Bandwidth
Uriel Feige and Kunal Talwar