{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T03:46:33Z","timestamp":1742960793361,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054352","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"23-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Facility location with dynamic distance functions"],"prefix":"10.1007","author":[{"given":"Randeep","family":"Bhatia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoram J.","family":"Sussmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1006\/jagm.1993.1047","volume":"15","author":"J. Bar-Ilan","year":"1993","unstructured":"J. Bar-Ilan, G. Kortsarz and D. Peleg, \u201cHow to allocate network centers\u201d, J. Algorithms, 15:385\u2013415, (1993).","journal-title":"J. Algorithms"},{"key":"3_CR2","unstructured":"R. Bhatia, S. Guha, S. Khuller and Y. J. Sussmann, \u201cFacility location with dynamic distance functions\u201d, Technical Report CS-TR-3834, UMIACS-TR-97-70, Univ of Maryland (1997)."},{"key":"3_CR3","volume-title":"Technical Report MPI-I-96-1-021","author":"S. Chaudhuri","year":"1996","unstructured":"S. Chaudhuri, N. Garg, and R. Ravi, \u201cBest possible approximation algorithms for generalized k-Center problems\u201d, Technical Report MPI-I-96-1-021, Max-Planck-Institut f\u00fcr Informatik, Im Stadtwald, 66123 Saarbr\u00fccken, Germany, (1996)."},{"key":"3_CR4","first-page":"741","volume":"35","author":"Z. Drezner","year":"1984","unstructured":"Z. Drezner, \u201cThe p-centre problem\u2014heuristic and optimal algorithms\u201d, J. Opl. Res. Soc. Vol 35:741\u2013748, (1984).","journal-title":"J. Opl. Res. Soc."},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0167-6377(85)90002-1","volume":"3","author":"M. Dyer","year":"1985","unstructured":"M. Dyer and A. M. Frieze, \u201cA simple heuristic for the p-center problem\u201d, Operations Research Letters, Vol 3:285\u2013288, (1985).","journal-title":"Operations Research Letters"},{"key":"3_CR6","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"M. R. Garey","year":"1978","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, 1978."},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T. Gonzalez","year":"1985","unstructured":"T. Gonzalez, \u201cClustering to minimize the maximum inter-cluster distance\u201d, Theoretical Computer Science, Vol 38:293\u2013306, (1985).","journal-title":"Theoretical Computer Science"},{"issue":"No1","key":"3_CR8","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R. Hassin","year":"1992","unstructured":"R. Hassin, \u201cApproximation schemes for the restricted shortest path problems\u201d, Mathematics of Operations Research, Vol 17:36\u201342, No 1. Feb. 1992.","journal-title":"Mathematics of Operations Research"},{"key":"3_CR9","unstructured":"D. Hochbaum, personal communication, Oct (1996)."},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"D. Hochbaum","year":"1985","unstructured":"D. Hochbaum and D. B. Shmoys, \u201cA best possible heuristic for the k-center problem\u201d, Mathematics of Operations Research, Vol 10:180\u2013184, (1985).","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"3_CR11","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D. Hochbaum","year":"1986","unstructured":"D. Hochbaum and D. B. Shmoys, \u201cA unified approach to approximation algorithms for bottleneck problems\u201d, Journal of the ACM, Vol 33(3):533\u2013550, (1986).","journal-title":"Journal of the ACM"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"W. L. Hsu","year":"1979","unstructured":"W. L. Hsu and G. L. Nemhauser, \u201cEasy and hard bottleneck location problems\u201d, Discrete Applied Mathematics, Vol 1:209\u2013216, (1979).","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0137040","volume":"37","author":"O. Kariv","year":"1979","unstructured":"O. Kariv and S. L. Hakimi, \u201cAn algorithmic approach to network location problems. I: The p-centers\u201d, SIAM J. Appl. Math, Vol 37:513\u2013538, (1979).","journal-title":"SIAM J. Appl. Math"},{"key":"3_CR14","first-page":"37","volume":"1203","author":"S. Khuller","year":"1997","unstructured":"S. Khuller, R. Pless, and Y. J. Sussmann, \u201cFault tolerant K-Center problems\u201d, Proc. of the 3\n                        \n                  rd\n                \n                        Italian Conference on Algorithms and Complexity, LNCS 1203, pages 37\u201348, (1997).","journal-title":"LNCS"},{"key":"3_CR15","first-page":"152","volume":"1136","author":"S. Khuller","year":"1996","unstructured":"S. Khuller and Y. J. Sussmann, \u201cThe capacitated K-Center problem\u201d, Proc. of the 4\n                        \n                  th\n                \n                        Annual European Symposium on Algorithms, LNCS 1136, pages 152\u2013166, (1996).","journal-title":"LNCS"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(95)00141-X","volume":"56","author":"S. O. Krumke","year":"1995","unstructured":"S. O. Krumke, \u201cOn a generalization of the p-center problem\u201d, Information Processing Letters, Vol 56:67\u201371, (1995).","journal-title":"Information Processing Letters"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1145\/359581.359591","volume":"20","author":"H. L. Morgan","year":"1977","unstructured":"H. L. Morgan and K. D. Levin, \u201cOptimal program and data locations in computer networks\u201d, Communications of the ACM, Vol 20:315\u2013322, (1977).","journal-title":"Communications of the ACM"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"K. Murthy and J. Kam, \u201cAn approximation algorithm to the file allocation problem in computer networks\u201d, Proc. of the 2\n                        \n                  nd\n                \n                        ACM Symposium on Principles of Database Systems, pages 258\u2013266, (1983).","DOI":"10.1145\/588058.588087"},{"key":"3_CR19","unstructured":"R. Panigrahy, \u201cAn O(log n) approximation algorithm for the asymmetric p-center problem\u201d, manuscript, 1995."},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0166-218X(87)90029-1","volume":"17","author":"J. Plesnik","year":"1987","unstructured":"J. Plesnik, \u201cA heuristic for the p-center problem in graphs\u201d, Discrete Applied Mathematics, Vol 17:263\u2013268, (1987)","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"R. Ravi, M. X. Goemans, \u201cThe constrained minimum spanning tree problem\u201d, SWAT 1996, 66\u201375.","DOI":"10.1007\/3-540-61422-2_121"},{"key":"3_CR22","unstructured":"D. Serra and V. Marianov, \u201cThe P-median problem in a changing network: The case of Barcelona\u201d, paper presented at the International Symposium in Locational Decisions VII, (ISOLDE), Edmonton, Canada, (1996)."},{"key":"3_CR23","doi-asserted-by":"crossref","first-page":"1363","DOI":"10.1287\/opre.19.6.1363","volume":"19","author":"C. Toregas","year":"1971","unstructured":"C. Toregas, R. Swain, C. Revelle and L. Bergman, \u201cThe location of emergency service facilities\u201d, Operations Research, Vol 19:1363\u20131373, (1971).","journal-title":"Operations Research"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"J. Van Leeuwen, Ed., Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, The MIT Press\/Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50015-1"},{"key":"3_CR25","unstructured":"S. Vishwanathan, \u201cAn O(log*\n                        n) approximation algorithm for the asymmetric p-Center problem\u201d, Proc. of the 7\n                        \n                  th\n                \n                        Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1\u20135, (1996)."},{"key":"3_CR26","unstructured":"Q. Wang and K. H. Cheng, \u201cA heuristic algorithm for the k-center problem with cost and usage weights\u201d, Proc. of the Twenty-Eighth Annual Allerton Conference on Communication, Control, and Computing, pages 324\u2013333, (1990)."},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1287\/opre.35.1.70","volume":"35","author":"A. Warburton","year":"1987","unstructured":"A. Warburton, \u201cApproximation of pareto optima in multiple-objective, shortest path problems\u201d, Operations Research Vol 35:70\u201379, (1987).","journal-title":"Operations Research"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T23:24:52Z","timestamp":1676676292000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054352"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/bfb0054352","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"26 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}