{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T17:59:18Z","timestamp":1794592758344,"version":"4.9.1"},"publisher-location":"New York, NY","reference-count":57,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_139","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:51:54Z","timestamp":1553097114000},"page":"717-724","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Facility Location"],"prefix":"10.1007","author":[{"given":"Karen","family":"Aardal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jaroslaw","family":"Byrka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Mahdian","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"139_CR61","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0020-0190(99)00144-1","volume":"72","author":"K Aardal","year":"1999","unstructured":"Aardal K, Chudak FA, Shmoys DB (1999) A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inf Process Lett 72:161\u2013167","journal-title":"Inf Process Lett"},{"key":"139_CR62","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0166-218X(99)00103-1","volume":"93","author":"AA Ageev","year":"1999","unstructured":"Ageev AA, Sviridenko MI (1999) An 0.828-approximation algorithm for the uncapacitated facility location problem. Discret Appl Math 93:149\u2013156","journal-title":"Discret Appl Math"},{"issue":"2","key":"139_CR63","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.ic.2004.06.002","volume":"194","author":"A Anagnostopoulos","year":"2004","unstructured":"Anagnostopoulos A, Bent R, Upfal E, van Hentenryck P (2004) A simple and deterministic competitive algorithm for online facility location. Inf Comput 194(2):175\u2013202","journal-title":"Inf Comput"},{"key":"139_CR64","doi-asserted-by":"crossref","unstructured":"Andrews M, Zhang L (1998) The access network design problem. In: Proceedings of the 39th annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Los Alamitos, pp 40\u201349","DOI":"10.1109\/SFCS.1998.743427"},{"key":"139_CR65","doi-asserted-by":"crossref","unstructured":"Arora S, Raghavan P, Rao S (1998) Approximation schemes for Euclidean k-medians and related problems. In: Proceedings of the 30th annual ACM symposium on theory of computing (STOC). ACM, New York, pp 106\u2013113","DOI":"10.1145\/276698.276718"},{"key":"139_CR66","doi-asserted-by":"crossref","unstructured":"Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V (2001) Local search heuristics for k-median and facility location problems. In: Proceedings of the 33rd annual ACM symposium on theory of computing (STOC). ACM, New York, pp 21\u201329","DOI":"10.1145\/380752.380755"},{"key":"139_CR67","unstructured":"Balinski ML (1966) On finding integer solutions to linear programs. In: Proceedings of the IBM scientific computing symposium on combinatorial problems. IBM, White Plains, pp 225\u2013248"},{"key":"139_CR68","unstructured":"Balinski ML, Wolfe P (1963) On Benders decomposition and a plant location problem. In: ARO-27. Mathematica Inc., Princeton"},{"key":"139_CR69","unstructured":"Beasley JE (2008) Operations research library. http:\/\/people.brunel.ac.uk\/~mastjjb\/jeb\/info.html. Accessed 2008"},{"key":"139_CR610","doi-asserted-by":"crossref","unstructured":"Byrka J (2007) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the 10th international workshop on approximation algorithms for combinatorial optimization problems (APPROX). Lecture notes in computer science, vol 4627. Springer, Berlin, pp 29\u201343","DOI":"10.1007\/978-3-540-74208-1_3"},{"key":"139_CR611","doi-asserted-by":"crossref","unstructured":"Charikar M, Guha S, Tardos E, Shmoys DB (1999) A constant factor approximation algorithm for the k-median problem. In: Proceedings of the 31st annual ACM symposium on theory of computing (STOC). ACM, New York, pp 1\u201310","DOI":"10.1145\/301250.301257"},{"key":"139_CR612","unstructured":"Charikar M, Khuller S, Mount D, Narasimhan G (2001) Facility location with outliers. In: Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM, Philadelphia, pp 642\u2013651"},{"issue":"1","key":"139_CR613","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"FA Chudak","year":"2003","unstructured":"Chudak FA, Shmoys DB (2003) Improved approximation algorithms for the uncapacitated facility location problem. SIAM J Comput 33(1):1\u201325","journal-title":"SIAM J Comput"},{"key":"139_CR614","doi-asserted-by":"crossref","unstructured":"Chudak FA, Wiliamson DP (1999) Improved approximation algorithms for capacitated facility location problems. In: Proceedings of the 7th conference on integer programing and combinatorial optimization (IPCO). Lecture notes in computer science, vol 1610. Springer, Berlin, pp 99\u2013113","DOI":"10.1007\/3-540-48777-8_8"},{"key":"139_CR615","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"8","author":"G Cornu\u00e9jols","year":"1977","unstructured":"Cornu\u00e9jols G, Fisher ML, Nemhauser GL (1977) Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag Sci 8:789\u2013810","journal-title":"Manag Sci"},{"key":"139_CR616","doi-asserted-by":"publisher","first-page":"992","DOI":"10.1287\/opre.26.6.992","volume":"26","author":"D Erlenkotter","year":"1978","unstructured":"Erlenkotter D (1978) A dual-based procedure for uncapacitated facility location problems. Oper Res 26:992\u20131009","journal-title":"Oper Res"},{"key":"139_CR617","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of ln n for approximating set cover. J ACM 45:634\u2013652","journal-title":"J ACM"},{"key":"139_CR618","doi-asserted-by":"crossref","unstructured":"Fotakis D (2003) On the competitive ratio for online facility location. In: Proceedings of the 30th international colloquium on automata, languages and programming (ICALP). Lecture notes in computer science, vol 2719. Springer, Berlin, pp 637\u2013652","DOI":"10.1007\/3-540-45061-0_51"},{"key":"139_CR619","doi-asserted-by":"crossref","unstructured":"Guha S, Khuller S (1998) Greedy strikes back: improved facility location algorithms. In: Proceedings of the 9th ACM-SIAM symposium on discrete algorithms (SODA). SIAM, Philadelphia, pp 228\u2013248","DOI":"10.1006\/jagm.1998.0993"},{"key":"139_CR620","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha S, Khuller S (1999) Greedy strikes back: improved facility location algorithms. J Algorithm 31:228\u2013248","journal-title":"J Algorithm"},{"key":"139_CR621","doi-asserted-by":"crossref","unstructured":"Guha S, Meyerson A, Munagala K (2001) A constant factor approximation for the single sink edge installation problem. In: Proceedings of the 33rd annual ACM symposium on theory of computing (STOC). ACM, New York, pp 383\u2013388","DOI":"10.1145\/380752.380827"},{"key":"139_CR622","doi-asserted-by":"crossref","unstructured":"Guha S, Meyerson A, Munagala K (2000) Hierarchical placement and network design problems. In: Proceedings of the 41st annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Los Alamitos, pp 603\u2013612","DOI":"10.1109\/SFCS.2000.892328"},{"key":"139_CR623","doi-asserted-by":"crossref","unstructured":"Gupta A, P\u00e1l M, Ravi R, Sinha A (2004) Boosted sampling: approximation algorithms for stochastic optimization. In: Proceedings of the 36st annual ACM symposium on theory of computing (STOC). ACM, New York, pp 417\u2013426","DOI":"10.1145\/1007352.1007419"},{"issue":"1","key":"139_CR624","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1002\/net.10080","volume":"42","author":"M Hajiaghayi","year":"2003","unstructured":"Hajiaghayi M, Mahdian M, Mirrokni VS (2003) The facility location problem with general cost functions. Networks 42(1):42\u201347","journal-title":"Networks"},{"issue":"2","key":"139_CR625","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum DS (1982) Heuristics for the fixed cost median problem. Math Program 22(2):148\u2013162","journal-title":"Math Program"},{"key":"139_CR626","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum DS, Shmoys DB (1985) A best possible approximation algorithm for the k-center problem. Math Oper Res 10:180\u2013184","journal-title":"Math Oper Res"},{"key":"139_CR627","doi-asserted-by":"crossref","unstructured":"Hoefer M (2003) Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location. In: Proceedings of the 2nd international workshop on experimental and efficient algorithms (WEA). Lecture notes in computer science, vol 2647. Springer, Berlin, pp 165\u2013178","DOI":"10.1007\/3-540-44867-5_13"},{"issue":"6","key":"139_CR628","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain K, Mahdian M, Markakis E, Saberi A, Vazirani VV (2003) Approximation algorithms for facility location via dual fitting with factor-revealing LP. J ACM 50(6):795\u2013824","journal-title":"J ACM"},{"key":"139_CR629","doi-asserted-by":"crossref","unstructured":"Jain K, Mahdian M, Saberi A (2002) A new greedy approach for facility location problems. In: Proceedings of the 34st annual ACM symposium on theory of computing (STOC). ACM, New York, pp 731\u2013740","DOI":"10.1145\/509907.510012"},{"key":"139_CR630","doi-asserted-by":"crossref","unstructured":"Jain K, Vazirani VV (2000) An approximation algorithm for the fault tolerant metric facility location problem. In: Approximation algorithms for combinatorial optimization, proceedings of APPROX. Lecture notes in computer science, vol 1913. Springer, Berlin, pp 177\u2013183","DOI":"10.1007\/3-540-44436-X_18"},{"key":"139_CR631","doi-asserted-by":"crossref","unstructured":"Jamin S, Jin C, Jin Y, Raz D, Shavitt Y, Zhang L (2000) On the placement of internet instrumentations. In: Proceedings of the 19th annual joint conference of the IEEE computer and communications Societies (INFOCOM), vol 1. IEEE Computer Society, Los Alamitos, pp 295\u2013304","DOI":"10.1109\/INFCOM.2000.832199"},{"key":"139_CR632","doi-asserted-by":"crossref","unstructured":"Karger D, Minkoff M (2000) Building Steiner trees with incomplete global knowledge. In: Proceedings of the 41st annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Los Alamitos, pp 613\u2013623","DOI":"10.1109\/SFCS.2000.892329"},{"key":"139_CR633","first-page":"1","volume-title":"Discrete location theory","author":"J Krarup","year":"1990","unstructured":"Krarup J, Pruzan PM (1990) Ingredients of locational analysis. In: Mirchandani P, Francis R (eds) Discrete location theory. Wiley, New York, pp 1\u201354"},{"key":"139_CR634","first-page":"38","volume":"12","author":"J Krarup","year":"1983","unstructured":"Krarup J, Pruzan PM (1983) The simple plant location problem: survey and synthesis. Eur J Oper Res 12:38\u201381","journal-title":"Eur J Oper Res"},{"key":"139_CR635","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"AA Kuehn","year":"1963","unstructured":"Kuehn AA, Hamburger MJ (1963) A heuristic program for locating warehouses. Manag Sci 9:643\u2013666","journal-title":"Manag Sci"},{"key":"139_CR636","doi-asserted-by":"crossref","unstructured":"Li B, Golin M, Italiano G, Deng X, Sohraby K (1999) On the optimal placement of web proxies in the internet. In: Proceedings of the 18th annual joint conference of the IEEE computer and communications societies (INFOCOM). IEEE Computer Society, Los Alamitos, pp 1282\u20131290","DOI":"10.1109\/INFCOM.1999.752146"},{"key":"139_CR637","unstructured":"Mahdian M (2004) Facility location and the analysis of algorithms through factor-revealing programs. PhD thesis, MIT, Cambridge"},{"key":"139_CR638","doi-asserted-by":"crossref","unstructured":"Mahdian M, P\u00e1l M (2003) Universal facility location. In: Proceedings of the 11th annual european symposium on algorithms (ESA). Lecture notes in computer science, vol 2832. Springer, Berlin, pp 409\u2013421","DOI":"10.1007\/978-3-540-39658-1_38"},{"issue":"2","key":"139_CR639","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M Mahdian","year":"2006","unstructured":"Mahdian M, Ye Y, Zhang J (2006) Approximation algorithms for metric facility location problems. SIAM J Comput 36(2):411\u2013432","journal-title":"SIAM J Comput"},{"key":"139_CR640","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1287\/mnsc.11.2.213","volume":"11","author":"AS Manne","year":"1964","unstructured":"Manne AS (1964) Plant location under economies-of-scale \u2013 decentralization and computation. Manag Sci 11:213\u2013235","journal-title":"Manag Sci"},{"key":"139_CR641","doi-asserted-by":"crossref","unstructured":"Meyerson A (2001) Online facility location. In: Proceedings of the 42nd annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Los Alamitos, pp 426\u2013431","DOI":"10.1109\/SFCS.2001.959917"},{"key":"139_CR642","volume-title":"Discrete location theory","author":"PB Mirchandani","year":"1990","unstructured":"Mirchandani PB, Francis RL (1990) Discrete location theory. Wiley, New York"},{"key":"139_CR643","volume-title":"Integer and combinatorial optimization","author":"GL Nemhauser","year":"1990","unstructured":"Nemhauser GL, Wolsey LA (1990) Integer and combinatorial optimization. Wiley, New York"},{"key":"139_CR644","doi-asserted-by":"crossref","unstructured":"P\u00e1l M, Tardos E, Wexler T (2001) Facility location with nonuniform hard capacities. In: Proceedings of the 42nd annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Los Alamitos, pp 329\u2013338","DOI":"10.1109\/SFCS.2001.959907"},{"key":"139_CR645","unstructured":"Qiu L, Padmanabhan VN, Voelker G (2001) On the placement of web server replicas. In: Proceedings of the 20th annual joint conference of the IEEE computer and communications societies (INFOCOM). IEEE Computer Society, Los Alamitos, pp 1587\u20131596"},{"issue":"1","key":"139_CR646","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10107-005-0673-5","volume":"108","author":"R Ravi","year":"2006","unstructured":"Ravi R, Sinha A (2006) Hedging uncertainty: approximation algorithms for stochastic optimization problems. Math Program 108(1):97\u2013114","journal-title":"Math Program"},{"key":"139_CR647","doi-asserted-by":"crossref","unstructured":"Ravi R, Sinha A (2002) Integrated logistics: approximation algorithms combining facility location and network design. In: Proceedings of the 9th conference on integer programming and combinatorial optimization (IPCO). Lecture notes in computer science, vol 2337. Springer, Berlin, pp 212\u2013229","DOI":"10.1007\/3-540-47867-1_16"},{"key":"139_CR648","unstructured":"Ravi R, Sinha A (2004) Multicommodity facility location. In: Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM, Philadelphia, pp 342\u2013349"},{"key":"139_CR649","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/3-540-44436-X_4","volume-title":"Approximation algorithms for combinatorial optimization","author":"DB Shmoys","year":"2000","unstructured":"Shmoys DB (2000) Approximation algorithms for facility location problems. In: Jansen K, Khuller S (eds) Approximation algorithms for combinatorial optimization, vol 1913, Lecture notes in computer science. Springer, Berlin, pp 27\u201333"},{"key":"139_CR650","first-page":"85","volume-title":"Proceedings of symposia in applied mathematics","author":"DB Shmoys","year":"2004","unstructured":"Shmoys DB (2004) The design and analysis of approximation algorithms: facility location as a case study. In: Thomas RR, Hosten S, Lee J (eds) Proceedings of symposia in applied mathematics, vol 61. AMS, Providence, pp 85\u201397"},{"key":"139_CR651","doi-asserted-by":"crossref","unstructured":"Shmoys DB, Tardos E, Aardal K (1997) Approximation algorithms for facility location problems. In: Proceedings of the 29th annual ACM symposium on theory of computing (STOC). ACM, New York, pp 265\u2013274","DOI":"10.1145\/258533.258600"},{"key":"139_CR652","doi-asserted-by":"crossref","unstructured":"Svitkina Z, Tardos E (2006) Facility location with hierarchical facility costs. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithm (SODA). SIAM, Philadelphia, pp 153\u2013161","DOI":"10.1145\/1109557.1109576"},{"issue":"4","key":"139_CR653","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C Swamy","year":"2004","unstructured":"Swamy C, Kumar A (2004) Primal-dual algorithms for connected facility location problems. Algorithmica 40(4):245\u2013269","journal-title":"Algorithmica"},{"key":"139_CR654","unstructured":"Swamy C, Shmoys DB (2003) Fault-tolerant facility location. In: Proceedings of the 14th annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM, Philadelphia, pp 735\u2013736"},{"key":"139_CR655","unstructured":"Vygen J (2005) Approximation algorithms for facility location problems (lecture notes). Technical report No. 05950-OR, Research Institute for Discrete Mathematics, University of Bonn. http:\/\/www.or.uni-bonn.de\/~vygen\/fl.pdf"},{"key":"139_CR656","doi-asserted-by":"crossref","unstructured":"Zhang J (2004) Approximating the two-level facility location problem via a quasi-greedy approach. In: Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM, Philadelphia, pp 808\u2013817. Also, Math Program 108:159\u2013176 (2006)","DOI":"10.1007\/s10107-006-0704-x"},{"issue":"2","key":"139_CR657","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1287\/moor.1040.0125","volume":"30","author":"J Zhang","year":"2005","unstructured":"Zhang J, Chen B, Ye Y (2005) A multiexchange local search algorithm for the capacitated facility location problem. Math Oper Res 30(2):389\u2013403","journal-title":"Math Oper Res"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_139","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:44:17Z","timestamp":1792107857000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_139"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_139","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}