{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T05:18:34Z","timestamp":1767676714183,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540200642"},{"type":"electronic","value":"9783540396581"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39658-1_6","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T23:24:30Z","timestamp":1279841070000},"page":"31-42","source":"Crossref","is-referenced-by-count":22,"title":["Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties"],"prefix":"10.1007","author":[{"given":"Aaron","family":"Archer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ranjithkumar","family":"Rajagopalan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David B.","family":"Shmoys","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"Ageev, A., Sviridenko, M.: An approximation algorithm for the uncapacitated facility location problem (manuscript) (1997)"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Bollobas, B., Lov\u00e1sz, L.: Proving integrality gaps without knowing the linear program. In: 43rd FOCS, pp. 313\u2013322 (2002)","DOI":"10.1109\/SFCS.2002.1181954"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for k-median and facility location problems. In: 33rd STOC, pp. 21\u201329 (2001)","DOI":"10.1145\/380752.380755"},{"key":"6_CR4","unstructured":"Balinski, M.: On finding integer solutions to linear programs. In: Proc. IBM Scientific Computing Symp. on Combinatorial Problems, pp. 225\u2013248 (1966)"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: 30th STOC, pp. 161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: 37th FOCS, pp. 184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: 40th FOCS, pp. 378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, E., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. In: 31st STOC, pp. 1\u201310 (1999)","DOI":"10.1145\/301250.301257"},{"key":"6_CR9","unstructured":"Chudak, F., Shmoys, D.B.: Improved approximation algorithms for uncapacitated facility location. SIAM J. Comput. (to appear)"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-45535-3_5","volume-title":"Integer Programming and Combinatorial Optimization","author":"F. Chudak","year":"2001","unstructured":"Chudak, F., Roughgarden, T., Williamson, D.P.: Approximate k-mSTs and k-steiner trees via the primal-dual method and lagrangean relaxation. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 60\u201370. Springer, Heidelberg (2001)"},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M. Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.P.: A general approximation technique for constrained forest problems. SICOMP\u00a024, 296\u2013317 (1995)","journal-title":"SICOMP"},{"key":"6_CR12","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.: Greedy strikes back: improved facility location algorithms. J. Alg.\u00a031, 228\u2013248 (1999)","journal-title":"J. Alg."},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D. Hochbaum","year":"1982","unstructured":"Hochbaum, D.: Heuristics for the fixed cost median problem. Math. Prog.\u00a022, 148\u2013162 (1982)","journal-title":"Math. Prog."},{"key":"6_CR14","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. To appear in JACM"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.: Approximation algorithms for metric facility location and k-median problems using primal-dual schema and Lagrangian relaxation. JACM\u00a048, 274\u2013296 (2001)","journal-title":"JACM"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Jain, K., Vazirani, V.: Primal-dual approximation algorithms for metric facility location and k-median problems. In: 40th FOCS, pp. 2\u201313 (1999)","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M. Korupolu","year":"2000","unstructured":"Korupolu, M., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Alg.\u00a037, 146\u2013188 (2000)","journal-title":"J. Alg."},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","volume":"44","author":"J.H. Lin","year":"1992","unstructured":"Lin, J.H., Vitter, J.: Approximation algorithms for geometric median problems. IPL\u00a044, 245\u2013249 (1992)","journal-title":"IPL"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M. Mahdian","year":"2002","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 229\u2013242. Springer, Heidelberg (2002)"},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N. Meggido","year":"1979","unstructured":"Meggido, N.: Combinatorial optimization with rational objective functions. Math. OR\u00a04, 414\u2013424 (1979)","journal-title":"Math. OR"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Mettu, R., Plaxton, C.G.: The online median problem. In: 41st FOCS, pp. 339\u2013348 (2000)","DOI":"10.1109\/SFCS.2000.892122"},{"key":"6_CR22","unstructured":"P\u00e1l, M., Tardos, \u00c9.: Strategy proof mechanisms via primal-dual algorithms. To appear in 44th FOCS (2003)"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems. In: 29th STOC, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"6_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/3-540-47867-1_18","volume-title":"Integer Programming and Combinatorial Optimization","author":"M. Sviridenko","year":"2002","unstructured":"Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 240\u2013257. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39658-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T07:37:38Z","timestamp":1740296258000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39658-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540200642","9783540396581"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39658-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}