{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:09:20Z","timestamp":1761620960191},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424703"},{"type":"electronic","value":"9783540446668"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44666-4_16","type":"book-chapter","created":{"date-parts":[[2007,5,3]],"date-time":"2007-05-03T12:58:07Z","timestamp":1178197087000},"page":"127-137","source":"Crossref","is-referenced-by-count":32,"title":["A Greedy Facility Location Algorithm Analyzed Using Dual Fitting"],"prefix":"10.1007","author":[{"given":"Mohammad","family":"Mahdian","sequence":"first","affiliation":[]},{"given":"Evangelos","family":"Markakis","sequence":"additional","affiliation":[]},{"given":"Amin","family":"Saberi","sequence":"additional","affiliation":[]},{"given":"Vijay","family":"Vazirani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"M. Charikar and S. Guha. Improved combinatorial algorithms for facility location and k-median problems. Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 378\u2013388, October 1999.","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"16_CR2","unstructured":"M. Charikar, S. Khuller, D. Mount, and G. Narasimhan. Algorithms for Facility Location Problems with Outliers. Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, 2001."},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"F. Chudak and D. Shmoys. Improved approximation algorithms for the capacitated facility location problem. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 875\u2013876, 1999.","DOI":"10.1007\/3-540-48777-8_8"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"V. Chvatal. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, pp. 233\u2013235, 1979.","journal-title":"Math. Oper. Res."},{"key":"16_CR5","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. Journal of Algorithms 31, pp. 228\u2013248, 1999.","journal-title":"Journal of Algorithms"},{"key":"16_CR6","unstructured":"S. Guha, A. Meyerson, and K. Munagala. Improved Approximation Algorithms for Fault-tolerant Facility Location. Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, 2001."},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D. S. Hochbaum","year":"1982","unstructured":"D. S. Hochbaum. Heuristics for the fixed cost median problem. Math. Programming 22, 148\u2013162, 1982.","journal-title":"Math. Programming"},{"key":"16_CR8","unstructured":"K. Jain, M. Mahdian, and A. Saberi. A new greedy approach for facility location problems, manuscript."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"K. Jain and V. V. Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 2\u201313, October 1999.","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"16_CR10","first-page":"177","volume":"2000","author":"K. Jain","year":"2000","unstructured":"K. Jain and V. Vazirani. An approximation algorithm for the fault tolerant metric facility location problem. Proceedings of APPROX 2000, pp. 177\u2013183, 2000.","journal-title":"Proceedings of APPROX"},{"key":"16_CR11","unstructured":"M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1\u201310, January 1998."},{"key":"16_CR12","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"A. A. Kuehn","year":"1963","unstructured":"A. A. Kuehn and M. J. Hamburger. A heuristic program for locating warehouses. Management Science 9, pp. 643\u2013666, 1963.","journal-title":"Management Science"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lovasz","year":"1975","unstructured":"L. Lovasz. On the ratio of Optimal Integral and Fractional Covers. Discrete Math. 13, pp. 383\u2013390, 1975.","journal-title":"Discrete Math."},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"R. Mettu and G. Plaxton. The online median problem. Proceedings of 41st IEEE FOCS, 2000.","DOI":"10.1109\/SFCS.2000.892122"},{"key":"16_CR15","first-page":"526","volume":"28","author":"S. Rajagopalan","year":"1999","unstructured":"S. Rajagopalan and V. V. Vazirani. Primal-dual RNC approximation of covering integer programs. SIAM J. Comput. 28, pp. 526\u2013541, 1999.","journal-title":"SIAM J. Comput."},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, E. Tardos, and K. Aardal. Approximation algorithms for facility location problems. Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265\u2013274, May 1997.","DOI":"10.1145\/258533.258600"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"M. Thorup. Quick k-median, k-center, and facility location for sparse graphs. To appear in ICALP 2001.","DOI":"10.1007\/3-540-48224-5_21"},{"key":"16_CR18","volume-title":"Approximation Algorithms","author":"V. V. Vazirani","year":"2001","unstructured":"V. V. Vazirani. Approximation Algorithms, Springer-Verlag, Berlin, 2001."}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44666-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T13:26:31Z","timestamp":1556371591000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44666-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424703","9783540446668"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-44666-4_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}