On the continuous Weber and k-median problems (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the continuous Weber and k-median problems (extended abstract)

Full text

Pdf (1.16 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the sixteenth annual symposium on Computational geometry table of contents

Clear Water Bay, Kowloon, Hong Kong

Pages: 70 - 79

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Sándor P. Fekete	Fachbereich Mathematik, Technische Universität Berlin, 10623 Berlin, Germany
Joseph S. B. Mitchell	Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, NY
Karin Weinbrecht	Zentrum für Angewandte Informatik, Universität zu Köln, 50923 Köln, Germany

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 47, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/336154.336182 What is a DOI?

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	Pankaj K. Agarwal , Micha Sharir , Emo Welzl, The discrete 2-center problem, Proceedings of the thirteenth annual symposium on Computational geometry, p.147-155, June 04-06, 1997, Nice, France [doi>10.1145/262839.262921]
	2	Y. P. Aneja and M. Parlar. Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel. Transportation Science, 28(1):70-76, 1994.
	3	Chanderjit Bajaj, The algebraic degree of geometric optimization problems, Discrete & Computational Geometry, v.3 n.2, p.177-191, Jan, 1988 [doi>10.1007/BF02187906]
	4	R. Batta, A. Ghose, and U. S. Palekax. Locating facilities on the Manhattan metric with arbitrarily shaped barriers and convex forbidden regions. Transportation Science, 23(1):26-36, 1989.
	5	Margaret L. Brandeau , Samuel S. Chiu, An overview of representative problems in location research, Management Science, v.35 n.6, p.645-674, June 1989 [doi>10.1287/mnsc.35.6.645]
	6	E. Carrizosa , M. Muñoz-Márquez , J. Puerto, Location and shape of a rectangular facility in Rⁿ : convexity properties, Mathematical Programming: Series A and B, v.83 n.2, p.277-290, Oct. 1, 1998
	7	E. Carrizosa, M. Mufioz-M~quez, and J. Puerto. The Weber problem with regional demand. European Journal of Operational Research, 104:358-365, 1998.
	8	Timothy M. Chan, More planar two-center algorithms, Computational Geometry: Theory and Applications, v.13 n.3, p.189-198, Sept. 1999 [doi>10.1016/S0925-7721(99)00019-X]
	9	R. Chandrasekaran , A. Tamir, Algebraic optimization: the Fermat-Weber location problem, Mathematical Programming: Series A and B, v.46 n.2, p.219-224, Feb. 1990 [doi>10.1007/BF01585739]
	10	Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
	11	R. Chert and G. Y. Handler. The conditional p-center problem in the Plane. Naval Research Logistics, 40:117- 127, 1993.
	12	Victor Chepoi, A multifacility location problem on median spaces, Discrete Applied Mathematics, v.64 n.1, p.1-29, Jan. 4, 1996 [doi>10.1016/0166-218X(95)00115-8]
	13	Yi-Jen Chiang , Joseph S. B. Mitchell, Two-point Euclidean shortest path queries in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.215-224, January 17-19, 1999, Baltimore, Maryland, United States
	14	Joonsoo Choi , Chan-Su Shin , Sung Kwon Kim, Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles, Proceedings of the 9th International Symposium on Algorithms and Computation, p.29-38, December 14-16, 1998
	15	Z. Drezner. On the rectangular p-center problem. Naval Res. Logist. Q., 34:229-234, 1987.
	16	Z. Drezner. Facility Location: A Survey of Applications and Methods. Springer Series in Operations Research. Springer-Verlag, New York, 1995.
	17	Z. Drezner. Replacing discrete demand with continuous demand. In Z. Drezner, editor, Facility Location: A Survey of Applications and Methods, Springer Series in Operations Research, chapter 2. Springer-Verlag, New York, 1995.
	18	Z. Drezner and G. O. Wesolowsky. Optimal location of a facility relative to area demands. Naval Research Logistics Quarterly, 27:199-206, 1980.
	19	R. Durier and C. Michelot. On the set of optimal points to the Weber problem: further results. Transportation Science, 28(2):141-149, 1994.
	20	David Eppstein, Faster construction of planar two-centers, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.131-138, January 05-07, 1997, New Orleans, Louisiana, United States
	21	A. J. Goldman. Optimal center location in simple networks. Transp. Sci., 5:240-255, 1971.
	22	H. W. Hamacher and S. Nickel. Classification of location problems. Location Science, 6:229-242, 1998.
	23	John Hershberger, A faster algorithm for the two-center decision problem, Information Processing Letters, v.47 n.1, p.23-29, Aug. 9, 1993 [doi>10.1016/0020-0190(93)90153-Z]
	24	John Hershberger , Subhash Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, v.28 n.6, p.2215-2256, Dec. 1999 [doi>10.1137/S0097539795289604]
	25	D. S. Hochbaum and D. Shmoys. A best possible heuristic for the k-center problem. Math. Oper. Res., 10:180- 184, 1985.
	26	R. Z. Hwang, R. C. T. Lee, and R. C. Chang. The slab dividing approach to solve the Euclidean p-center problem. Algorithmica, 9:1-22, 1993.
	27	O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems, i: The p-centers. SIAM J. Appl. Math., 37:513-538, 1979.
	28	Samir Khuller , Yoram J. Sussmann, The Capacitated K-Center Problem (Extended Abstract), Proceedings of the Fourth Annual European Symposium on Algorithms, p.152-166, September 25-27, 1996
	29	M. T. Ko , Y. T. Ching, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l∞ -distance, Discrete Applied Mathematics, v.40 n.3, p.397-410, Dec. 14, 1992 [doi>10.1016/0166-218X(92)90009-Y]
	30	M. T. Ko, R. C. T. Lee, and J. S. Chang. An optimal approximation algorithm for the rectilinear m-center problem. Algorithmica, 5:341-352, 1990.
	31	A. Kolen. Equivalence between the direct search approach and the cut approach to the rectilinear distance location problem. Operations Research, 29(3):616-620, 1981.
	32	Yoshiyuki Kusakari , Takao Nishizeki, An Algorithm for Finding a Region with the Minimum Lotal L1 from Prescribed Terminals, Proceedings of the 8th International Symposium on Algorithms and Computation, p.324-333, December 17-19, 1997
	33	R. C. Larson and G. Sadiq. Facility locations with the Manhattan metric in the presence of barriers to travel. Operations Research, 31(4):652-669, 1983.
	34	R. F. Love, J. G. Morris, and G. O. Wesolowsky. Facilities Location: Models ~ Methods. North Hollandde Gruyter, New York, 1988.
	35	N. Megiddo. The weighted Euclidean 1-center problem. Math. Oper. Res., 8(4):498-504, 1983.
	36	N. Megiddo and A. Tamir. New results on the complexity of p-center problems. SIAM J. Comput., 12:751-758, 1983.
	37	N. Megiddo and E. Zemel. A randomized O(n log n) algorithm for the weighted Euclidean 1-center problem. J. Algorithms, 7:358-368, 1986.
	38	P. B. Mirchandani and R. L. Francis, editors. Discrete Location Theory. Wiley, New Yorkl, 1990.
	39	J. S. B. Mitchell. An optimal algorithm for shortest rectilinear paths among obstacles, in Abstracts 1st Canad. Conf. Comput. Geom., page 22, 1989.
	40	J. S. B. Mitchell. A new algorithm for shortest paths among obstacles in the plane. Ann. Math. Artif. Intell., 3:83-106, 1991.
	41	J. S. B. Mitchell. L1 shortest paths among polygonal obstacles in the plane. Algorithmica, 8:55-88, 1992.
	42	Joseph S. B. Mitchell, Shortest paths and networks, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	43	J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, page to appear. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 1999.
	44	C. Papadimitriou. Worst case and probabilistic analysis of a geometric location problem. SIAM J. Computing, 3:542-557, 1981.
	45	F. Plastria. Continuous location problems. In Z. Drezner, editor, Facility Location: A Survey of Applications and Methods, Springer Series in Operations Research, chapter 11. Springer-Verlag, New York, 1995.
	46	R. Pollack , M. Sharir , G. Rote, Computing the geodesic center of a simple polygon, Discrete & Computational Geometry, v.4 n.6, p.611-626, Sep. 1989 [doi>10.1007/BF02187751]
	47	P. Rosenstiehl and R. E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete and Computational Geometry, 1:343-353, 1986.
	48	M. Sharir. A near-linear algorithm for the planar 2- center problem. Discrete Comput. Geom., 18:125-134, 1997.
	49	Micha Sharir , Emo Welzl, Rectilinear and polygonal p-piercing and p-center problems, Proceedings of the twelfth annual symposium on Computational geometry, p.122-132, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237255]
	50	Hanif D. Sherali , Frederick L. Nordai, NP-Hard, capacitated, balanced p-median problems on a chain graph with a continuum of link demands, Mathematics of Operations Research, v.13 n.1, p.32-49, February 1988 [doi>10.1287/moor.13.1.32]
	51	Arie Tamir, On the solution value of the continuous P-center location problem on a graph, Mathematics of Operations Research, v.12 n.2, p.340-349, May 1987 [doi>10.1287/moor.12.2.340]
	52	A. Weber. Ober den Standort der Industrien, 1. Teil: Reine Theorie des Standortes. Tiibingen, Germany, 1909.
	53	K. Weinbrecht. Kontinuierliche Standortprobleme in Polygonen. PhD thesis, Universit~it zu KSln, 1999.
	54	G. Wesolowsky. The Weber problem: History and perspective. Location Science, 1:5-23, 1993.
	55	G. O. Wesolowsky and R. F. Love. Location of facilities with rectangular distances among point and area destinations. Naval Research Logistics Quarterly, 18:83-90, 1971.
	56	G. O. Wesolowsky and R. F. Love. The optimal location of new facilities using rectangular distances. Operations Research, 19:124-130, 1971.
	57	G. O. Wesolowsky and R. F. Love. A nonlinear approximation method for solving a generalized rectangular distance Weber problem. Management Science, 11:656-663, 1972.
	58	E. Zemel. Probabilistic analysis of geometric location problems. SIAM J. Alg. and Discrete Methods, 6:189- 200, 1985.

CITED BY 3

	Sándor P. Fekete , Henk Meijer, The one-round Voronoi game replayed, Computational Geometry: Theory and Applications, v.30 n.2, p.81-94, February 2005
	Ali Ahmadinia , Christophe Bobda , Sandor P. Fekete , Jurgen Teich , Jan C. van der Veen, Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices, IEEE Transactions on Computers, v.56 n.5, p.673-680, May 2007
	A. Karim Abu-Affash , Matthew J. Katz, Improved bounds on the average distance to the Fermat--Weber center of a convex object, Information Processing Letters, v.109 n.6, p.329-333, February, 2009