List of accepted papers for APPROX 2004:


Approximating Max kCSP using random restrictions
Gustav Hast

On systems of linear equations with two variables per equation
Uriel Feige and Daniel Reichman

Randomized Approximation Algorithms for Set Multicover Problems with Applications to
Reverse Engineering of Protein and Gene Networks
Piotr Berman and Bhaskar DasGupta and Eduardo Sontag

Approximating additive distortion of metric embeddings
Kedar Dhamdhere

Polylogarithmic inapproximability of Radio Broadcast
Michael Elkin and Guy Kortsarz

On the Crossing Spanning Tree Problem
Vittorio Bilo and Vineet Goyal and R. Ravi and Mohit Singh

Centralized deterministic broadcasting in undirected multi-hop
Dariusz R. Kowalski and Andrzej Pelc

A 3/4-approximation algorithm for Maximum ATSP with weights zero and one
Markus Blaeser

Computationally-Feasible Truthful Auctions for Convex Bundles
Moshe Babaioff and Liad Blumrosen

Min-Max Multiway Cut
Zoya Svitkina and Eva Tardos

Cost Sharing Mechanisms for Network Design
Anupam Gupta and Aravind Srinivasan and Eva Tardos

Approximation Schemes for Broadcasting in Heterogenous Networks
Samir Khuller and Yoo-Ah Kim

Convergence Issues in Competitive Games
Vahab S. Mirrokni and Adrian Vetta

Maximum Coverage Problem with Group Budget Constraints and Applications to Repairman Problems
C. Chekuri and A. Kumar

The greedy algorithm for the minimum common partition problem
Marek Chrobak and Petr Kolman and Jiri Sgall

Designing Networks with Existing Traffic to Support Fast Restoration
Mansoor Alicherry and Randeep Bhatia and Yung-Chun (Justin) Wan

Approximating Market Equilbrium-The Separable Gross Substitutibility Case
Rahul Garg and Sanjiv Kapoor and Vijay Vazirani

Simultaneous Source Location
Konstantin Andreev and Charles Garrod and Bruce Maggs and Adam Meyerson

Cuts and Orderings: On semidefinite relaxations for the linear ordering problem
Alantha Newman