{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:38:30Z","timestamp":1742387910840},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_23","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:32:38Z","timestamp":1188336758000},"page":"260-271","source":"Crossref","is-referenced-by-count":3,"title":["The k-Median Problem for Directed Trees"],"prefix":"10.1007","author":[{"given":"Marek","family":"Chrobak","sequence":"first","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","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"A. Aggarwal, M. M. Klawe, S. Moran, and R. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195\u2013208, 1987.","journal-title":"Algorithmica"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, P. Raghavan, and S. Rao. Approximation schemes for euclidean k-medians and related problems. In Proc. 30th Annual ACM Symposium on Theory of Computing (STOC\u201998), pages 106\u2013113, 1998.","DOI":"10.1145\/276698.276718"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0304-3975(96)00089-8","volume":"165","author":"V. Auletta","year":"1996","unstructured":"V. Auletta, D. Parente, and G. Persiano. Dynamic and static algorithms for optimal placement of resources in a tree. Theoretical Computer Science, 165:441\u2013461, 1996.","journal-title":"Theoretical Computer Science"},{"key":"23_CR4","first-page":"87","volume":"26","author":"V. Auletta","year":"1998","unstructured":"V. Auletta, D. Parente, and G. Persiano. Placing resources on a growing line. Journal of Algorithms, 26:87\u2013100, 1998.","journal-title":"Journal of Algorithms"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"M. Charikar and S. Guha. Improved combinatorial algorithms for facility location and k-median problems. In Proc. 40th Symposium on Foundations of Computer Science (FOCS\u201999), pages 378\u2013388, 1999.","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"M. Charikar, S. Guha, E. Tardos, and D. Shmoys. A constant-factor approximation algorithm for the k-median problem. In Proc. 31st Annual ACM Symposium on Theory of Computing (STOC\u201999), 1999.","DOI":"10.1145\/301250.301257"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"684","DOI":"10.2307\/2373068","volume":"87","author":"H. Davenport","year":"1965","unstructured":"H. Davenport and A. Schinzel. A combinatorial problem connected with differential equations. American J. Math., 87:684\u2013694, 1965.","journal-title":"American J. Math."},{"key":"23_CR8","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: a Guide to the Theory of NP-completeness. W. H. Freeman and Co., 1979."},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1002\/net.3230260413","volume":"26","author":"R. Gavish","year":"1995","unstructured":"R. Gavish and S. Sridhar. Computing the 2-median on tree networks in O(n log n) time. Networks, 26:305\u2013317, 1995.","journal-title":"Networks"},{"key":"23_CR10","unstructured":"M. H. Halldorson, K. Iwano, N. Katoh, and T. Tokuyama. Finding subsets maximizing minimum structures. In Proc. 6th Annual Symposium on Discrete Algorithms (SODA\u2019 95), pages 150\u2013157, 1995."},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0167-6377(91)90041-M","volume":"10","author":"R. Hassin","year":"1991","unstructured":"R. Hassin and A. Tamir. Improved complexity bounds for location problems on the real line. Operation Research Letters, 10:395\u2013402, 1991.","journal-title":"Operation Research Letters"},{"key":"23_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":"W. L. Hsu. The distance-domination numbers of trees. Operation Research Letters, 1:96\u2013100, 1982.","journal-title":"Operation Research Letters"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0137041","volume":"37","author":"O. Kariv","year":"1979","unstructured":"O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems II: The p-medians. SIAM Journal on Applied Mathematics, 37:539\u2013560, 1979.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M. R. Korupolu","year":"2000","unstructured":"M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37:146\u2013188, 2000.","journal-title":"Journal of Algorithms"},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"B. Li, X. Deng, M. Golin, and K. Sohraby. On the optimal placement of web proxies on the Internet: linear topology. In Proc. 8th IFIP Conference on High Peformance Netwworking (HPN\u201998), pages 00\u201300, 1998.","DOI":"10.1007\/978-0-387-35388-3_28"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"B. Li, M. J. Golin, G. F. Italiano, X. Deng, and K. Sohraby. On the optimal placement of web proxies in the Internet. In IEEE InfoComm\u201999, pages 1282\u20131290, 1999.","DOI":"10.1109\/INFCOM.1999.752146"},{"key":"23_CR17","unstructured":"M. Sharir and P. K. Agarwal. Davenport-Schinzel sequences and their geometric applications. Cambridge University Press, 1995."},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0167-6377(96)00021-1","volume":"19","author":"A. Tamir","year":"1996","unstructured":"A. Tamir. An O(pn 2) algorithm for the p-median and related problems on tree graphs. Operations Research Letters, 19:59\u201364, 1996.","journal-title":"Operations Research Letters"},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0020-0190(00)00026-0","volume":"74","author":"A. Vigneron","year":"2000","unstructured":"A. Vigneron, L. Gao, M. Golin, G. Italiano, and B. Li. An algorithm for finding a k-median in a directed tree. Information Processing Letters, 74:81\u201388, 2000.","journal-title":"Information Processing Letters"},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0167-6377(00)00041-9","volume":"27","author":"G. Woeginger","year":"2000","unstructured":"G. Woeginger. Monge strikes again: optimal placement of web proxies in the Internet. Operations Research Letters, 27:93\u201396, 2000.","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:27:55Z","timestamp":1556803675000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}