{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T05:04:29Z","timestamp":1740287069679,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540406716"},{"type":"electronic","value":"9783540451389"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45138-9_16","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T22:41:48Z","timestamp":1277246508000},"page":"218-227","source":"Crossref","is-referenced-by-count":6,"title":["Faster Algorithms for k-Medians in Trees"],"prefix":"10.1007","author":[{"given":"Robert","family":"Benkoczi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binay","family":"Bhattacharya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lawrence L.","family":"Larmore","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for euclidean k-medians and related problems. In: Proc. 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Mungala, K., Pandit, V.: Local seach heuristic for k-median and facility location problems. In: Proc. 16th Annual ACOM Symposium on Computing, pp. 21\u201329 (2001)","DOI":"10.1145\/380752.380755"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0304-3975(96)00089-8","volume":"165","author":"V. Auletta","year":"1996","unstructured":"Auletta, V., Parente, D., Persiano, G.: Dynamic and static algorithms for optimal placement of resources in a tree. Theoretical Computer Science\u00a0165, 441\u2013461 (1996)","journal-title":"Theoretical Computer Science"},{"key":"16_CR4","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":"16_CR5","unstructured":"Benkoczi, R.R., Bhattacharya, B.K.: Spine tree decomposition. Technical Report CMPT1999-09, School of Computing Science, Simon Fraser University, Canada (1999)"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and k-median problems. In: Proc. 40th Symposium on Foundations of Computer Science (FOCS 1999), pp. 378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, E., Shmoys, D.: A constant-factor approximation algorithm for the k-median problem. In: Proc. 31st Annual ACM Symposium on Theory of Computing (STOC 1999), pp. 1\u201310 (1999)","DOI":"10.1145\/301250.301257"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/3-540-44683-4_23","volume-title":"Mathematical Foundations of Computer Science 2001","author":"M. Chrobak","year":"2001","unstructured":"Chrobak, M., Larmore, L., Rytter, W.: The k-median problem for directed trees. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a0136, pp. 260\u2013271. Springer, Heidelberg (2001)"},{"key":"16_CR9","volume-title":"Computers and Intractability: a Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-completeness. W.H. Freeman and Co., New York (1979)"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1002\/net.3230260413","volume":"26","author":"R. Gavish","year":"1995","unstructured":"Gavish, R., Sridhar, S.: Computing the 2-median on tree networks in $O(n \\ {\\log} \\ n)$ time. Networks\u00a026, 305\u2013317 (1995)","journal-title":"Networks"},{"key":"16_CR11","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. Operation Research Letters\u00a010, 395\u2013402 (1991)","journal-title":"Operation Research Letters"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0167-6377(82)90005-0","volume":"1","author":"W.L. Hsu","year":"1982","unstructured":"Hsu, W.L.: The distance-domination numbers of trees. Operation Research Letters\u00a01, 96\u2013100 (1982)","journal-title":"Operation Research Letters"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0137041","volume":"37","author":"O. Kariv","year":"1979","unstructured":"Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems II: The p-medians. SIAM Journal on Applied Mathematics\u00a037, 539\u2013560 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M.R. Korupolu","year":"2000","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. Journal of Algorithms\u00a037, 146\u2013188 (2000)","journal-title":"Journal of Algorithms"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Li, B., Deng, X., Golin, M., Sohraby, K.: On the optimal placement of web proxies on the internet: linear topology. In: Proc. 8th IFIP Conference on High Peformance Netwworking (HPN 1998), pp. 485\u2013495 (1998)","DOI":"10.1007\/978-0-387-35388-3_28"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Li, B., Golin, M.J., Italiano, G.F., Deng, X., Sohraby, K.: On the optimal placement of web proxies in the internet. In: IEEE InfoComm 1999, pp. 1282\u20131290 (1999)","DOI":"10.1109\/INFCOM.1999.752146"},{"key":"16_CR17","unstructured":"Shah, R., Farach-Colton, M.: Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees. In: Proc. 13th Annual Symposium on Discrete Algorithms (SODA), pp. 108\u2013115 (2002)"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Shah, R., Langerman, S., Lodha, S.: Algorithms for efficient filtering in contentbased multicast. In: Proc. 9th Annual European Symposium on Algorithms (ESA), pp. 428\u2013439 (2001)","DOI":"10.1007\/3-540-44676-1_36"},{"key":"16_CR19","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(pn 2) algorithm for the p-median and related problems on tree graphs. Operations Research Letters\u00a019, 59\u201364 (1996)","journal-title":"Operations Research Letters"},{"key":"16_CR20","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":"16_CR21","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","Mathematical Foundations of Computer Science 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45138-9_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T05:07:47Z","timestamp":1740200867000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45138-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540406716","9783540451389"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45138-9_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}