Moses Charikar
Sudipto Guha
Éva Tardos
- 1.S. Arora, P. Raghavan and S. Rao. Approximation schemes for Euclidean k-medians and related problems. Proceedings of the 30th Annual A CM Symposium on Theory of Computing, pp. 106-113, 1998.]] Google Scholar
Digital Library
- 2.J. Bar-Ilan, G. Kortsarz, and D. Peleg. How to allocate network centers. J. Algorithms, 15:385- 415, 1993.]] Google ScholarDigital Library
- 3.Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pages 184-193, 1996.]] Google ScholarDigital Library
- 4.Y. Baxtal. On approximating arbitrary metrics by tree metrics. In Proceedings of the 30th Annual A CM Symposium on Theory of Computing, pages 161-168, 1998.]] Google ScholarDigital Library
- 5.M. Charikar, C. Chekuri, A. Goel, and S. Guha. Rounding via trees: deterministic approximation algorithms for group Steiner crees and k-median. In Proceedings of the $Oth Annual A CM Symposium on Theory of Computing, pages 114-123, 1998.]] Google ScholarDigital Library
- 6.F. A. Chudak. Improved approximation algorithms for uncapacitated facility location. In R. E. Bixby, E. A. Boyd, and R. Z. Rfos-Mercado, editors, Integer Programming and Combinatorial Optimization, volume 1412 of Lecture Notes in Computer Science, pages 180-194, Berlin, 1998. Springer.]]Google Scholar
- 7.F. Chudak and D. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. Unpublished manuscript, 1998.]]Google Scholar
- 8.F. A. Chudak and 'D. B. Shmoys. Improved approximation algorithms for the capacitaterl facility location problem. In Proceedings of the l Oth Annual A CM-SIAM Symposium on Discrete Algorithms, pages $875-S876, t999.]] Google ScholarDigital Library
- 9.G. Cornu~jols, G. L. Nemhauser, and L. A. Wolsey. The uncapacitated facility location problem. In P. Mirchandani and R. Francis, editors, Discrete Location Theory, pages 119- I71. John WiIey and Sons, Inc., New York, 1990.]]Google Scholar
- 10.M. E. Dyer and A. M. Frieze. A simple heuristic for the p-center problem. Oper. Res. Lett., 3:285-288, 1985.]]Google ScholarDigital Library
- 11.T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. $ci., 38:293-306, 1985.]]Google Scholar
- 12.S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. In Proceedings of the 9th Ar~nual A CM-SIAM Symposium on Discrete Algorithms, pages 649-657, 1998.]] Google ScholarDigital Library
- 13.D. S. Hochbaum and D. B. Shmoys. A best possible approximation algorithm for the k-center problem. Math. Oper. Res., 10:180-184, 1985.]]Google ScholarDigital Library
- 14.O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems, Part II: pmedians. SIAM J. Appl. Math., 37:539-560, 1979.]]Google ScholarCross Ref
- 15.S. Khuller and Y. J. Sussmann. The capacitated k-center problem. In Proceedings ol~ the ,~th Annual European Symposium on Algorithms, Lecture Notes in Computer Science 1136, pages 152-166, Berlin, 1996. Springer.]] Google ScholarDigital Library
- 16.M. R. Korupolu, C. G. Ptaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems, in Proceedings of the 9th Annual A CM-$IAM Symposium on Discrete Algorithms, pages 1-10, 1998.]] Google ScholarDigital Library
- 17.J.-H. Lin and J. S. Vitter. Approximation algorithms for geometric median problems. Inform. Proc. Lett., 44:245-249, 1992.]] Google ScholarDigital Library
- 18.J.-H. Lin and J. S. Vitter. ~-approximations with minimum packing constraint violation. In Proceedings of the 24fth Armual A CM Symposium on Thecry of Computing, pages 771-782, 1992.]] Google ScholarDigital Library
- 19.D. B. Shmoys and E. Tardos. An Approximation Algorithm for the Generalized Assignment Problem. Math. Programming, 62:461-474, 1993.]]Google ScholarDigital Library
- 20.D. B. Shmoys, I~. Tardos, and K. I. Aardal. Approximation algorithms for facility location problems. In Proceedings ojr the 29th Annual A CM Symposium on Theory of Computing, pages 265-274, 1997.]] Google ScholarDigital Library
- 21.M. Sviridenko. Personal communication, July, 1998.]]Google Scholar
- 22.A. Tamir. An O(/m2) algorithm for the p-median and related problems on tree graphs. Oper. Res. Lett., 19:59-94, 1996.]]Google ScholarDigital Library
- 23.S. de Vries, M. Posner, and R. Vohra. The K- median Problem on a Tree. Working paper, Ohio State University, Oct. 1998.]]Google Scholar
- 24.J. Ward, R. T. Wong, P. Lemke, and A. Oudjit. Properties of the tree K-median linear programming relaxation. Unpublished manuscript, 1994.]]Google Scholar
Index Terms
- A constant-factor approximation algorithm for the k-median problem (extended abstract)
Recommendations
A Constant Factor Approximation Algorithm for the Storage Allocation Problem
We study the storage allocation problem (SAP) which is a variant of the unsplittable flow problem on paths (UFPP). A SAP instance consists of a path $$P = (V,E)$$P=(V,E) and a set J of tasks. Each edge $$e \in E$$e E has a capacity $$c_e$$ce and each ...
A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
In this article, we consider the fault-tolerant k-median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of the classical k-median problem, each client j needs to be assigned to at least rj ...
Constant-factor approximation for ordered k-median
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingWe study the Ordered k-Median problem, in which the solution is evaluated by first sorting the client connection costs and then multiplying them with a predefined non-increasing weight vector (higher connection costs are taken with larger weights). ...
Comments