3 papers
cs.DS2008
Simpler Analyses of Local Search Algorithms for Facility Location
Anupam Gupta, Kanat Tangwongsan
We study local search algorithms for metric instances of facility location problems: the uncapacitated facility location problem (UFL), as well as uncapacitated versions of the …
cs.DM2007
How to Complete a Doubling Metric
Anupam Gupta, Kunal Talwar
In recent years, considerable advances have been made in the study of properties of metric spaces in terms of their doubling dimension. This line of research has not only enhanced…
cs.DS2007
Dial a Ride from k-forest
Anupam Gupta, MohammadTaghi Hajiaghayi, Viswanath Nagarajan +1
The k-forest problem is a common generalization of both the k-MST and the dense--subgraph problems. Formally, given a metric space on vertices , with demand pairs $\s…