K-medians, facility location, and the Chernoff-Wald bound

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

K-medians, facility location, and the Chernoff-Wald bound

Full text

Pdf (917 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 86 - 95

Year of Publication: 2000

ISBN:0-89871-453-2

Author

Neal E. Young

Department of Computer Science, Dartmouth College, Hanover, NH

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 40, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
	2	Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
	3	V. Chvatal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233-235, 1979.
	4	Lisa Fleischer. Unpublished manuscript. 1999.
	5	Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
	6	Naveen Garg. Unpublished manuscript. Distributed at Dagst/ihl, 1998.
	7	Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.649-657, January 25-27, 1998, San Francisco, California, United States
	8	Dorit S. Hochbaum. Heuristics for the fixed cost median problem. Math. Programming, 22(2):148-162, 1982.
	9	David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256-278, 1974.
	10	Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
	11	L~szl6 Lov~sz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975.
	12	George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
	13	Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995
	14	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	15	David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
	16	Neal E. Young, Randomized rounding without solving the linear program, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.170-178, January 22-24, 1995, San Francisco, California, United States

CITED BY 3

	R. C. Chakinala , A. Kumarasubramanian , K. A. Laing , R. Manokaran , C. Pandu Rangan , R. Rajaraman, Playing push vs pull: models and algorithms for disseminating dynamic data in networks, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Adam Meyerson , Liadan O'Callaghan , Serge Plotkin, A k-Median Algorithm with Running Time Independent of Data Size, Machine Learning, v.56 n.1-3, p.61-87