{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:44:25Z","timestamp":1792111465543,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":18,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_25","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:52Z","timestamp":1461269032000},"page":"113-116","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"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","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"25_CR1445","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N Alon","year":"1995","unstructured":"Alon N, Karp RM, Peleg D, West D (1995) A graph-theoretic game and its application to the k-server problem. SIAM J Comput 24:78\u2013100","journal-title":"SIAM J Comput"},{"key":"25_CR1446","doi-asserted-by":"crossref","unstructured":"Bartal Y (1996) 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. IEEE Computer Society, pp 184\u2013193","DOI":"10.1109\/SFCS.1996.548477"},{"key":"25_CR1447","doi-asserted-by":"crossref","unstructured":"Bartal Y (1998) On approximating arbitrary metrices by tree metrics. In: STOC '98: proceedings of the thirtieth annual ACM symposium on theory of computing. ACM Press, New York, pp 161\u2013168","DOI":"10.1145\/276698.276725"},{"key":"25_CR1448","doi-asserted-by":"crossref","unstructured":"Bartal Y, Charikar M, Raz D (2001) Approximating min-sum k-clustering in metric spaces. In: STOC '01: proceedings of the thirtythird annual ACM symposium on theory of computing. ACM Press, New York, pp 11\u201320","DOI":"10.1145\/380752.380754"},{"key":"25_CR1449","unstructured":"Calinescu G, Karloff H, Rabani Y (2001) Approximation algorithms for the 0-extension problem. In: SODA '01: proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, pp 8\u201316"},{"key":"25_CR1450","doi-asserted-by":"crossref","unstructured":"Charikar M, Chekuri C, Goel A, Guha S (1998) 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. ACM Press, New York, pp 114\u2013123","DOI":"10.1145\/276698.276719"},{"key":"25_CR1451","doi-asserted-by":"crossref","unstructured":"Elkin M, Emek Y, Spielman DA, Teng S-H (2005) Lower-stretch spanning trees. In: STOC '05: proceedings of the thirty-seventh annual ACM symposium on theory of computing. ACM Press, New York, pp 494\u2013503","DOI":"10.1145\/1060590.1060665"},{"key":"25_CR1452","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 (2004) Approximating metrics by tree metrics. SIGACT News 35:60\u201370","journal-title":"SIGACT News"},{"key":"25_CR1453","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 (2004) A tight bound on approximating arbitrary metrics by tree metrics. J Comput Syst Sci 69:485\u2013497","journal-title":"J Comput Syst Sci"},{"key":"25_CR1454","unstructured":"Gupta A (2001) Steiner points in tree metrics don't (really) help. In: SODA '01: proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, pp 220\u2013227"},{"key":"25_CR1455","doi-asserted-by":"crossref","unstructured":"Gupta A, Hajiaghayi MT, R\u00e4cke H (2006) Oblivious network design. In: SODA '06: proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithm. ACM Press, New York, pp 970\u2013979","DOI":"10.1145\/1109557.1109665"},{"key":"25_CR1456","doi-asserted-by":"crossref","unstructured":"Gupta A, Talwar K (2006) Approximating unique games. In: SODA '06: proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithm, New York. ACM Press, New York, pp 99\u2013106","DOI":"10.1145\/1109557.1109569"},{"key":"25_CR1457","unstructured":"Hayrapetyan A, Swamy C, Tardos \u00c9 (2005) Network design for information networks. In: SODA '05: proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, pp 933\u2013942"},{"key":"25_CR1458","doi-asserted-by":"crossref","unstructured":"Indyk P, Matousek J (2004) Low-distortion embeddings of finite metric spaces. In: Goodman JE, O'Rourke J (eds) Handbook of discrete and computational geometry. Chapman&Hall\/CRC, Boca Raton, chap. 8","DOI":"10.1201\/9781420035315.ch8"},{"key":"25_CR1459","unstructured":"Karp R (1989) A 2k-competitive algorithm for the circle. Manuscript"},{"key":"25_CR1460","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 (2002) Lectures on discrete geometry. Springer, New York"},{"key":"25_CR1461","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/PL00009336","volume":"19","author":"Y Rabinovich","year":"1998","unstructured":"Rabinovich Y, Raz R (1998) Lower bounds on the distortion of embedding finite metric spaces in graphs. Discret Comput Geom 19:79\u201394","journal-title":"Discret Comput Geom"},{"key":"25_CR1462","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"PD Seymour","year":"1995","unstructured":"Seymour PD (1995) Packing directed circuits fractionally. Combinatorica 15:281\u2013288","journal-title":"Combinatorica"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:50:59Z","timestamp":1792108259000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_25","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}