{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:33:05Z","timestamp":1725489185814},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441861"},{"type":"electronic","value":"9783540457534"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45753-4_5","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T11:37:09Z","timestamp":1187264229000},"page":"26-39","source":"Crossref","is-referenced-by-count":10,"title":["On the Power of Priority Algorithms for Facility Location and Set Cover"],"prefix":"10.1007","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Allan","family":"Borodin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"key":"5_CR1","unstructured":"A. Borodin, M. Nielsen, and C. Rackoff. (Incremental) priority algorithms. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 752\u2013761, 2002."},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"M. Charikar, C. Chekuri, T. Feder, and M. Motwani. Incremental clustering and dynamic information retrieval. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 626\u2013634, 1997.","DOI":"10.1145\/258533.258657"},{"issue":"3","key":"5_CR3","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"V. Chv\u00e1tal. A greedy heuristic for the set covering problem. Mathematics of Operations Research, 4(3):233\u2013235, 1979.","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"5_CR4","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 the ACM, 45(4):634\u2013652, 1998.","journal-title":"Journal of the ACM"},{"key":"5_CR5","unstructured":"S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pages 649\u2013657, 1998."},{"key":"5_CR6","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. Mathematical Programming, 22:148\u2013162, 1982.","journal-title":"Mathematical Programming"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"K. Jain, M. Mahdian, and A. Saberi. A new greedy approach for facility location problems. In Proceedings of the 34th Annual ACM Symposium on Theory of Computation, pages 731\u2013740, 2002.","DOI":"10.1145\/509907.510012"},{"issue":"3","key":"5_CR8","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256\u2013278, 1974.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383\u2013390, 1975.","journal-title":"Discrete Mathematics"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani. A greedy facility location algorithm analyzed using dual fitting. In Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 127\u2013137, 2001.","DOI":"10.1007\/3-540-44666-4_16"},{"key":"5_CR11","unstructured":"M. Mahdian, J. Ye, and J. Zhang. A 1.52-approximation algorithm for the uncapacitated facility location problem. Available at \n                  http:\/\/www.mit.edu\/~mahdian\/pub.html\n                  \n                ."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"R. R. Mettu and C. G. Plaxton. The online median problem. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pages 339\u2013348, 2000.","DOI":"10.1109\/SFCS.2000.892122"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"A. Meyerson. Online facility location. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 426\u2013431, 2001.","DOI":"10.1109\/SFCS.2001.959917"},{"key":"5_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_4","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"D.B. Shmoys","year":"2000","unstructured":"D.B. Shmoys. Approximation algorithms for facility location problems. In K. Jansen and S. Khuller, editors, Approximation Algorithms for Combinatorial Optimization, volume 1913 of Lecture Notes in Computer Science. Springer, Berlin, 2000."},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"D.B. Shmoys, E. Tardos, and K. Aardal. Approximation algorithms for facility location problems (extended abstract). In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 265\u2013274, 1997.","DOI":"10.1145\/258533.258600"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/jagm.1997.0887","volume":"25","author":"P. Slav\u00edk","year":"1997","unstructured":"P. Slav\u00edk. A tight analysis of the greedy algorithm for set cover. Journal of Algorithms, 25:237\u2013254, 1997.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45753-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T23:47:57Z","timestamp":1550792877000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45753-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441861","9783540457534"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-45753-4_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}