{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:33:18Z","timestamp":1794357198687,"version":"4.9.0"},"publisher-location":"Boston, MA","reference-count":18,"publisher":"Springer US","isbn-type":[{"value":"9780387307701","type":"print"},{"value":"9780387301624","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_25","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T14:37:51Z","timestamp":1214491071000},"page":"51-53","source":"Crossref","is-referenced-by-count":1,"title":["Approximating Metric Spaces by Tree Metrics"],"prefix":"10.1007","author":[{"given":"Jittat","family":"Fakcharoenphol","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"25_CR1_25","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N. Alon","year":"1995","unstructured":"Alon, N., Karp, R.M., Peleg, D., West, D.: A\u00a0graph\u2010theoretic game and its application to the k-server problem. SIAM J. Comput. 24, 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"key":"25_CR2_25","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: FOCS '96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, Washington, DC, USA, IEEE Computer Society, pp.\u00a0184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"25_CR3_25","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1145\/276698.276725","volume-title":"STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing","author":"Y. Bartal","year":"1998","unstructured":"Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp.\u00a0161\u2013168. ACM Press, New York (1998)"},{"key":"25_CR4_25","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/380752.380754","volume-title":"STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing","author":"Y. Bartal","year":"2001","unstructured":"Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum k\u2011clustering in metric spaces. In: STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp.\u00a011\u201320. ACM Press, New York (2001)"},{"key":"25_CR5_25","unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: Approximation algorithms for the 0\u2011extension problem. In: SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp.\u00a08\u201316. (2001)"},{"key":"25_CR6_25","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/276698.276719","volume-title":"STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing","author":"M. Charikar","year":"1998","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S.: Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median. In: STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp.\u00a0114\u2013123. ACM Press, New York (1998)"},{"key":"25_CR7_25","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1145\/1060590.1060665","volume-title":"STOC '05: Proceedings of the thirty\u2010seventh annual ACM symposium on Theory of computing","author":"M. Elkin","year":"2005","unstructured":"Elkin, M., Emek, Y., Spielman, D.A., Teng, S.-H.: Lower-stretch spanning trees. In: STOC '05: Proceedings of the thirty\u2010seventh annual ACM symposium on Theory of computing, pp.\u00a0494\u2013503. ACM Press, New York (2005)"},{"key":"25_CR8_25","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/992287.992300","volume":"35","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: Approximating metrics by tree metrics. SIGACT News 35, 60\u201370 (2004)","journal-title":"SIGACT News"},{"key":"25_CR9_25","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A\u00a0tight bound on approximating arbitrary metrics by tree metrics. J.\u00a0Comput. Syst. Sci. 69, 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR10_25","unstructured":"Gupta, A.: Steiner points in tree metrics don't (really) help. In: SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp.\u00a0220\u2013227. (2001)"},{"key":"25_CR11_25","doi-asserted-by":"publisher","first-page":"970","DOI":"10.1145\/1109557.1109665","volume-title":"SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm","author":"A. Gupta","year":"2006","unstructured":"Gupta, A., Hajiaghayi, M.T., R\u00e4cke, H.: Oblivious network design. In: SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp.\u00a0970\u2013979. ACM Press, New York (2006)"},{"key":"25_CR12_25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/1109557.1109569","volume-title":"SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, New York, NY, USA","author":"A. Gupta","year":"2006","unstructured":"Gupta, A., Talwar, K.: Approximating unique games. In: SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, New York, NY, USA, pp.\u00a099\u2013106. ACM Press, New York (2006)"},{"key":"25_CR13_25","unstructured":"Hayrapetyan, A., Swamy, C., Tardos, \u00c9.: Network design for information networks. In: SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp.\u00a0933\u2013942. (2005)"},{"key":"25_CR14_25","doi-asserted-by":"crossref","unstructured":"Indyk, P., Matousek, J.: Low\u2010distortion embeddings of finite metric spaces. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry. CRC Press, Inc., Chap.\u00a08 (2004), To appear","DOI":"10.1201\/9781420035315.ch8"},{"key":"25_CR15_25","unstructured":"Karp, R.: A\u00a02k-competitive algorithm for the circle. Manuscript (1989)"},{"key":"25_CR16_25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matousek","year":"2002","unstructured":"Matousek, J.: Lectures on Discrete Geometry. Springer, New York (2002)"},{"key":"25_CR17_25","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/PL00009336","volume":"19","author":"Y. Rabinovich","year":"1998","unstructured":"Rabinovich, Y., Raz, R.: Lower bounds on the distortion of embedding finite metric spaces in graphs. Discret. Comput. Geom. 19, 79\u201394 (1998)","journal-title":"Discret. Comput. Geom."},{"key":"25_CR18_25","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P.D. Seymour","year":"1995","unstructured":"Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15, 281\u2013288 (1995)","journal-title":"Combinatorica"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T16:32:57Z","timestamp":1738254777000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_25"}},"subtitle":["1996; Bartal, Fakcharoenphol, Rao, Talwar 2004; Bartal, Fakcharoenphol, Rao, Talwar"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_25","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2008]]}}}