{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:37Z","timestamp":1725558997799},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_10","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:27:29Z","timestamp":1279042049000},"page":"102-113","source":"Crossref","is-referenced-by-count":1,"title":["Online Maintenance of k-Medians and k-Covers on a Line"],"prefix":"10.1007","author":[{"given":"Rudolf","family":"Fleischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mordecai J.","family":"Golin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"10_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica\u00a02(2), 195\u2013208 (1987)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, pp. 106\u2013113 (1998)","key":"10_CR2","DOI":"10.1145\/276698.276718"},{"key":"10_CR3","first-page":"87","volume":"26","author":"V. Auletta","year":"1998","unstructured":"Auletta, V., Parente, D., Persiano, G.: Placing resources on a growing line. Journal of Algorithms\u00a026, 87\u2013100 (1998)","journal-title":"Journal of Algorithms"},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Guha, S., Tardos, E., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. Journal Computer System Sciences\u00a065, 129\u2013149 (2002)","journal-title":"Journal Computer System Sciences"},{"unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 649\u2013657 (1998)","key":"10_CR5"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0167-6377(91)90041-M","volume":"10","author":"R. Hassin","year":"1991","unstructured":"Hassin, R., Tamir, A.: Improved complexity bounds for location problems on the real line. Operations Research Letters\u00a010, 395\u2013402 (1991)","journal-title":"Operations Research Letters"},{"doi-asserted-by":"crossref","unstructured":"Lin, J.-H., Vitter, J.S.: \u03b5-approximations with minimum packing constraint violation. In: Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, pp. 771\u2013782 (1992)","key":"10_CR7","DOI":"10.1145\/129712.129787"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0167-6377(96)00021-1","volume":"19","author":"A. Tamir","year":"1996","unstructured":"Tamir, A.: An O(pn2) algorithm for the p-median and related problems on tree graphs. Operations Research Letters\u00a019, 59\u201364 (1996)","journal-title":"Operations Research Letters"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/0196-6774(88)90032-6","volume":"9","author":"R. Wilber","year":"1988","unstructured":"Wilber, R.: The concave least-weight subsequence problem revisited. Journal of Algorithms\u00a09, 418\u2013425 (1988)","journal-title":"Journal of Algorithms"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0020-0190(00)00026-0","volume":"74","author":"A. Vigneron","year":"2000","unstructured":"Vigneron, A., Gao, L., Golin, M., Italiano, G., Li, B.: An algorithm for finding a k-median in a directed tree. Information Processing Letters\u00a074, 81\u201388 (2000)","journal-title":"Information Processing Letters"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0167-6377(00)00041-9","volume":"27","author":"G. Woeginger","year":"2000","unstructured":"Woeginger, G.: Monge strikes again: optimal placement of web proxies in the internet. Operations Research Letters\u00a027, 93\u201396 (2000)","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:21:39Z","timestamp":1605759699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}