{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:16Z","timestamp":1774421296626,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540280613","type":"print"},{"value":"9783540318064","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_66","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T13:34:13Z","timestamp":1127828053000},"page":"654-660","source":"Crossref","is-referenced-by-count":6,"title":["The Reverse Greedy Algorithm for the Metric K-Median Problem"],"prefix":"10.1007","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[]},{"given":"Claire","family":"Kenyon","sequence":"additional","affiliation":[]},{"given":"Neal E.","family":"Young","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"66_CR1","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Munagala, K., Pandit, V.: Local search heuristic for k-median and facility location problems. In: Proc. 33rd ACM Symposium on Theory of Computing, pp. 21\u201329 (2001)","DOI":"10.1145\/380752.380755"},{"key":"66_CR2","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proc. 40th IEEE Symposium on Foundations of Computer Science, pp. 378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"66_CR3","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: Proc. 31st ACM Symposium on Theory of Computing, pp. 1\u201310 (1999)","DOI":"10.1145\/301250.301257"},{"issue":"4","key":"66_CR4","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of ACM"},{"key":"66_CR5","unstructured":"Fiat. Private communication"},{"key":"66_CR6","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D.S. Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Heuristics for the fixed cost median problem. Mathematical Programming\u00a022, 148\u2013162 (1982)","journal-title":"Mathematical Programming"},{"key":"66_CR7","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proc. 34th ACM Symposium on Theory of Computing, pp. 731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"key":"66_CR8","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of ACM\u00a048, 274\u2013296 (2001)","journal-title":"Journal of ACM"},{"key":"66_CR9","doi-asserted-by":"crossref","unstructured":"Lin, J.-H., Vitter, J.S.: e-approximations with minimum packing constraint violation (extended abstract). In: Proc. 24th ACM Symposium on Theory of Computing, pp. 771\u2013782 (1992)","DOI":"10.1145\/129712.129787"},{"key":"66_CR10","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"R. Mettu","year":"2003","unstructured":"Mettu, R., Plaxton, C.: The online median problem. SIAM Journal on Computing\u00a032, 816\u2013832 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"66_CR11","unstructured":"Young, N.E.: K-medians, facility location, and the Chernoff-Wald bound. In: Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 86\u201395 (2000)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_66","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T22:36:57Z","timestamp":1586471817000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/11533719_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}