{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T01:09:49Z","timestamp":1662167389110},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540436768","type":"print"},{"value":"9783540478676","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-47867-1_18","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T18:47:17Z","timestamp":1179946037000},"page":"240-257","source":"Crossref","is-referenced-by-count":74,"title":["An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem"],"prefix":"10.1007","author":[{"given":"Maxim","family":"Sviridenko","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,5,21]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0020-0190(99)00144-1","volume":"72","author":"K. Aardal","year":"1999","unstructured":"K. Aardal, F. Chudak and D. Shmoys, A 3-approximation algorithm for the k-level uncapacitated facility location problem, Inform. Process. Lett. 72 (1999), 161\u2013167.","journal-title":"Inform. Process. Lett."},{"key":"18_CR2","unstructured":"A. Ageev, An approximation scheme for the uncapacitated facility location problem on planar graphs, manuscript."},{"key":"18_CR3","first-page":"1","volume-title":"Proceedings of the First IPCO Conference","author":"A. Ageev","year":"1990","unstructured":"A. Ageev and V. Beresnev, Polynomially solvable special cases of the simple plant location problem, in: R. Kannan and W. Pulleyblank (eds.), Proceedings of the First IPCO Conference, Waterloo University Press, Waterloo, 1990, 1\u20136."},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0166-218X(99)00103-1","volume":"93","author":"A. Ageev","year":"1999","unstructured":"A. Ageev and M. Sviridenko, An 0.828-approximation algorithm for the uncapacitated facility location problem, Discrete Appl. Math. 93 (1999), 149\u2013156.","journal-title":"Discrete Appl. Math."},{"key":"18_CR5","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3-540-48777-8_2","volume-title":"Integer programming and combinatorial optimization (Graz, 1999)","author":"A. Ageev","year":"1999","unstructured":"A. Ageev and M. Sviridenko, Approximation algorithms for maximum coverage and max cut with given sizes of parts, Integer programming and combinatorial optimization (Graz, 1999), 17\u201330, Lecture Notes in Comput. Sci., 1610, Springer, Berlin, 1999."},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1137\/S089548010036813X","volume":"14","author":"A. Ageev","year":"2001","unstructured":"A. Ageev, R Hassin and M. Sviridenko, An 0.5-Approximation Algorithm for the MAX DICUT with given sizes of parts, SIAM Journal of Discrete Mathematics v. 14 (2001), pp. 246\u2013255","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"18_CR7","unstructured":"A. Ageev and M. Sviridenko, An approximation algorithm for Hypergraph Max Cut with given sizes of parts, in Proceedings of European Simposium on Algorithms (ESA00)."},{"key":"18_CR8","first-page":"106","volume-title":"STOC\u2019 98 (Dallas, TX)","author":"S. Arora","year":"1999","unstructured":"S. Arora, P. Raghavan and S. Rao, Approximation schemes for Euclidean k- medians and related problems, STOC\u2019 98 (Dallas, TX), 106\u2013113, ACM, New York, 1999."},{"key":"18_CR9","unstructured":"V. Arya, N. Garg, R. Khandekar, V. Pandit, A. Meyerson and K. Munagala, Local Search Heuristics for k-median and Facility Location Problems, to appear in STOC01."},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"M. Charikar and S. Guha, Improved Combinatorial Algorithms for Facility Location and K-Median Problems, In Proceedings of IEEE Foundations of Computer Science, 1999.","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"18_CR11","unstructured":"M. Charikar, S. Khuller, G. Narasimhan and D. Mount, Facility Location with Outliers, in Proceedings of Symposium on Discrete Algorithms (SODA), (Jan 2001)."},{"key":"18_CR12","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/3-540-69346-7_14","volume-title":"Integer programming and combinatorial optimization (Houston, TX, 1998)","author":"F. Chudak","year":"1998","unstructured":"F. Chudak, Improved approximation algorithms for uncapacitated facility location, Integer programming and combinatorial optimization (Houston, TX, 1998), 180\u2013194, Lecture Notes in Comput. Sci. 1412, Springer, Berlin, 1998."},{"key":"18_CR13","unstructured":"F. Chudak and D. Shmoys, Improved approximation algorithms for the capacitated facility location problem, In the Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (1999), 875\u2013876."},{"key":"18_CR14","unstructured":"F. Chudak and D. Shmoys, Improved approximation algorithms for uncapacitated facility location, manuscript."},{"key":"18_CR15","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-48777-8_8","volume-title":"Integer programming and combinatorial optimization (Graz, 1999)","author":"F. Chudak nad","year":"1999","unstructured":"F. Chudak nad D. Williamson, Improved approximation algorithms for capacitated facility location problems, Integer programming and combinatorial optimization (Graz, 1999), 99\u2013113, Lecture Notes in Comput. Sci., 1610, Springer, Berlin, 1999."},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G. Cornuejols","year":"1977","unstructured":"G. Cornuejols, M. L. Fisher and G. L. Nemhauser, Location of Bank Accounts to Optimize Float: An Analytic Study Exact and Approximate Algorithms, Management Science 23 (1977), 789\u2013810.","journal-title":"Management Science"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"U. Feige, A Threshold of ln n for Approximating Set Cover, Journal of ACM 45 (1998), 634\u2013652.","journal-title":"Journal of ACM"},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S. Guha","year":"1999","unstructured":"S. Guha and S. Khuller, Greedy strikes back: improved facility location algorithms, Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1998), J. Algorithms 31 (1999), 228\u2013248.","journal-title":"J. Algorithms"},{"key":"18_CR19","unstructured":"S. Guha, A. Meyerson and K. Munagala, Improved Algorithms for Fault Tolerant Facility Location, Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms, 2001."},{"key":"18_CR20","volume-title":"Inequalities","author":"G. Hardy","year":"1988","unstructured":"G. Hardy, J. Littlewood and G. P\u00f3lya, Inequalities, Reprint of the 1952 edition. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1988.","edition":"1952 edition"},{"key":"18_CR21","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D. Hochbaum","year":"1982","unstructured":"D. Hochbaum, Heuristics for the fixed cost median problem, Math. Programming 22 (1982), 148\u2013162.","journal-title":"Math. Programming"},{"key":"18_CR22","unstructured":"K. Jain, M. Mahdian and A. Saberi, A new greedy approach for facility location problems, to appear in STOC01."},{"key":"18_CR23","unstructured":"K. Jain and V. Vazirani, Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation, Proc. 1999 FOCS, to appear in JACM."},{"key":"18_CR24","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/3-540-48481-7_33","volume-title":"Algorithms\u2014ESA\u2019 99 (Prague)","author":"S. Kolliopoulos","year":"1999","unstructured":"S. Kolliopoulos and S. Rao, A nearly linear-time approximation scheme for the Euclidean k-median problem, Algorithms\u2014ESA\u2019 99 (Prague), 378\u2013389, Lecture Notes in Comput. Sci., 1643, Springer, Berlin, 1999."},{"key":"18_CR25","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M. Korupolu","year":"2000","unstructured":"M. Korupolu, G. Plaxton, and R. Rajaraman, Analysis of a local search heuristic for facility location problems, Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1998), J. Algorithms 37 (2000), 146\u2013188.","journal-title":"J. Algorithms"},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","volume":"44","author":"J. Lin","year":"1992","unstructured":"J. Lin and J. Vitter, Approximation algorithms for geometric median problems, Inform. Process. Lett. 44 (1992), 245\u2013249.","journal-title":"Inform. Process. Lett."},{"key":"18_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/3-540-44666-4_16","volume-title":"APPROX 2001","author":"M. Mahdian","year":"2001","unstructured":"M. Mahdian, E. Markakis, A. Saberi and V. Vazirani, A greedy facility location algorithm ananlyzed using dual fitting, APPROX 2001, LNCS 2129, pp. 127\u2013137."},{"key":"18_CR28","unstructured":"M. Mahdian, Y. Ye, and J. Zhang, A 1.52-Approximation Algorithm for the Uncapacitated Facility Location Problem, manuscript, 2002."},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"R. Mettu and G. Plaxton, The online median problem, In Proceedings of FOCS00, 339\u2013348.","DOI":"10.1109\/SFCS.2000.892122"},{"key":"18_CR30","unstructured":"A. Meyerson, K. Munagala and S. Plotkin, Web Caching using Access Statistics, in Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms, 2001."},{"key":"18_CR31","unstructured":"P. Mirchandani and R. Francis, eds. Discrete location theory, Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1990."},{"key":"18_CR32","doi-asserted-by":"crossref","unstructured":"D. Shmoys, E. Tardos and K. Aardal, Approximation algorithms for facility location problems, In 29th ACM Symposium on Theory of Computing (1997), 265\u2013274.","DOI":"10.1145\/258533.258600"},{"key":"18_CR33","first-page":"86","volume-title":"Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000)","author":"N. Young","year":"2000","unstructured":"N. Young, k-medians, facility location, and the Chernoff-Wald bound, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), 86\u201395, ACM, New York, 2000."}],"container-title":["Integer Programming and Combinatorial Optimization","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-47867-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T07:31:32Z","timestamp":1556436692000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-47867-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540436768","9783540478676"],"references-count":33,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-47867-1_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"published":{"date-parts":[[2002]]}}}