Quick and good facility location

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quick and good facility location

Full text

Pdf (766 KB)

Source

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

Baltimore, Maryland

SESSION: Session 3C table of contents

Pages: 178 - 185

Year of Publication: 2003

ISBN:0-89871-538-5

Author

Mikkel Thorup

AT&T Labs---Research, Florham Park, NJ

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 34, Citation Count: 4

Additional Information:

abstract 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

ABSTRACT

We consider the facility location problem with shortest path distances in a weighted graph. W.h.p., we get an approximation factor of 1.62 in O(n + m) time with n and m the number of nodes and edges. Also, as a kind of warm-up, for a metric with a constant-times distance oracle, we get the factor 1.62 deterministically in O(n² log n) time.Our results build on a recent facility location algorithm of Jain, Mahdian, and Saberi (STOC'02) achieving an approximation factor of 1.61 in O(n³) time.

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	Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534 ]
	2	Richard Cole , Ramesh Hariharan , Moshe Lewenstein , Ely Porat, A faster implementation of the Goemans-Williamson clustering algorithm, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.17-25, January 07-09, 2001, Washington, D.C., United States
	3	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	4	G. Cornuejols, G.L. Nemhauser, and L.A. Wolsley. The uncapacitated facility location problem. In P. Mirchandani and R. Francis, editors, Discrete Location Theory, pages 97--106. John-Wiley and Sons, Inc., 1986.
	5	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	6	Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Journal of Algorithms, v.31 n.1, p.228-248, April 1999 [doi>10.1006/jagm.1998.0993 ]
	7	S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
	8	Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301366]
	9	Kamal Jain , Mohammad Mahdian , Amin Saberi, A new greedy approach for facility location problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510012]
	10	S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. On the placement of Internet intrumentations. In Proc. 19th INFOCOM, pages 26--30, 2000.
	11	A.A. Kuehn and M.J. Hamburger. A heuristic prograom for locating warehouses. Management Science, 9:643--666, 1963.
	12	B. Li, M. Golin, G. G. Italiano, X. Deng, and K. Sohraby. On the optimal placement of web proxies in the Internet. In Proc. 18th INFOCOM, pages 1282--1290, 1999.
	13	Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani, A Greedy Facility Location Algorithm Analyzed Using Dual Fitting, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.127-137, August 18-20, 2001
	14	M. Mahdian, Y. Ye, and J. Zhang. Improved approximation algorithms for metric facility location problems, 2002.
	15	R. R. Mettu , C. G. Plaxton, The online median problem, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.339, November 12-14, 2000
	16	L. Qiu, V. N. Padmanabhan, and G. M. Voelker. On the optimal placement of web server replicas. In Proc. 20th INFOCOM, pages 1587--1596, 2001.
	17	B.C. Tansel, R.L. Francis, and T.J. Lowe. Location on networks: A survey, part 1 and 2. Management Science, 29(4):482--511, 1983.
	18	Mikkel Thorup, Quick k-Median, k-Center, and Facility Location for Sparse Graphs, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.249-260, July 08-12, 2001

CITED BY 4

	C. Greg Plaxton, Approximation algorithms for hierarchical location problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	C. Greg Plaxton, Approximation algorithms for hierarchical location problems, Journal of Computer and System Sciences, v.72 n.3, p.425-443, May 2006
	Nattaphol Jariyakul , Taieb Znati, An Optimized Clustering and Selective Probing Framework to Support Internet Quality-of-Service Routing, Simulation, v.82 n.5, p.311-330, May 2006
	P. A. Bonatti , P. Festa, On optimal service selection, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan