{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T05:30:32Z","timestamp":1740547832156,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212362"},{"type":"electronic","value":"9783540247494"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24749-4_21","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T19:01:54Z","timestamp":1283972514000},"page":"234-245","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithms for Minimizing Average Distortion"],"prefix":"10.1007","author":[{"given":"Kedar","family":"Dhamdhere","sequence":"first","affiliation":[]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","unstructured":"Agarwala, R., Bafna, V., Farach, M., Narayanan, B.O., Paterson, M., Thorup, M.: On the approximability of numerical taxonomy (fitting distances by tree metrics). In: SODA, pp. 365\u2013372 (1996)"},{"issue":"1","key":"21_CR2","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 graph-theoretic game and its application to the k-server problem. SIAM J. Comput.\u00a024(1), 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"key":"21_CR3","unstructured":"Archer, A., Levin, A., Williamson, D.P.: A faster, better approximation algorithm for the minimum latency problem. Cornell ORIE Technical Report number 1362 (2003)"},{"key":"21_CR4","unstructured":"Archer, A., Williamson, D.P.: Faster approximation algorithms for the minimum latency problem. In: SODA (2003)"},{"issue":"5","key":"21_CR5","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Arora, S., Karakostas, G.: Approximation schemes for minimum latency problems. In: Proceedings of the ACM STOC, pp. 688\u2013693 (1999)","DOI":"10.1145\/301250.301432"},{"issue":"1","key":"21_CR7","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1137\/S0097539794285983","volume":"27","author":"Y. Aumann","year":"1998","unstructured":"Aumann, Y., Rabani, Y.: An o(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput.\u00a027(1), 291\u2013301 (1998)","journal-title":"SIAM J. Comput."},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: IEEE FOCS, pp. 184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Blum, A., Burch, C., Tomkins, A.: A polylog(n)- competitive algorithm for metrical task systems. In: Proceedings of STOC, pp. 711\u2013719 (1997)","DOI":"10.1145\/258533.258667"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: Proceedings of the ACM STOC, pp. 163\u2013171 (1994)","DOI":"10.1145\/195058.195125"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Blum, A., Konjevod, G., Ravi, R., Vempala, S.: Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. In: Proceedings of the 30th ACM STOC, pp. 100\u2013105 (1998)","DOI":"10.1145\/276698.276717"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J. Bourgain","year":"1985","unstructured":"Bourgain, J.: On lipshitz embedding of finite metric spaces in hilbert space. Israel J. Math.\u00a052, 46\u201352 (1985)","journal-title":"Israel J. Math."},{"key":"21_CR13","unstructured":"Calinescu, G., Karloff, H.J., Rabani, Y.: Approximation algorithms for the 0-extension problem. In: SODA, pp. 8\u201316 (2001)"},{"key":"21_CR14","unstructured":"Fakcharoenphol, J., Harrelson, C., Rao, S.: The k-traveling repairman problem. In: SODA: 14th ACM-SIAM Symposium on Discrete Algorithms (2003)"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the 35th Annual ACM STOC, pp. 448\u2013455 (2003)","DOI":"10.1145\/780542.780608"},{"issue":"1\/2","key":"21_CR16","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01188585","volume":"13","author":"M. Farach","year":"1995","unstructured":"Farach, M., Kannan, S., Warnow, T.: A robust model for finding optimal evolutionary trees. Algorithmica\u00a013(1\/2), 155\u2013179 (1995)","journal-title":"Algorithmica"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Feige, U.: Approximating the bandwidth via volume respecting embeddings (extended abstract). In: Proc. 30th ACM STOC, pp. 90\u201399 (1998)","DOI":"10.1145\/276698.276716"},{"key":"21_CR18","unstructured":"Garg, Konjevod, Ravi: A polylogarithmic approximation algorithm for the group steiner tree problem. In: SODA (1998)"},{"key":"21_CR19","unstructured":"Garg, N.: Personal communication (September 2000)"},{"key":"21_CR20","unstructured":"Goemans, Kleinberg: An improved approximation ratio for the minimum latency problem. In: SODA (1996)"},{"key":"21_CR21","unstructured":"Gupta, A.: Steiner nodes in trees don\u2019t (really) help. In: SODA (2001)"},{"key":"21_CR22","unstructured":"Indyk, P.: Algorithmic aspects of geometric embeddings. In: IEEE FOCS (2001)"},{"issue":"1","key":"21_CR23","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P.N. Klein","year":"1995","unstructured":"Klein, P.N., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted steiner trees. J. Algorithms\u00a019(1), 104\u2013115 (1995)","journal-title":"J. Algorithms"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M., Tardos, E.: Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. In: IEEE FOCS, pp. 14\u201323 (1999)","DOI":"10.1109\/SFFCS.1999.814572"},{"volume-title":"The Traveling Salesman Problem","year":"1985","key":"21_CR25","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.): The Traveling Salesman Problem. John Wiley & Sons, Chichester (1985)"},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"Leighton, F.T., Rao, S.: An approximate max-flow mincut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proc. of the 29th IEEE FOCS, pp. 422\u2013431 (1988)","DOI":"10.1109\/SFCS.1988.21958"},{"key":"21_CR27","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica\u00a015, 215\u2013245 (1995)","journal-title":"Combinatorica"},{"issue":"3","key":"21_CR28","first-page":"589","volume":"31","author":"J. Matou\u0161ek","year":"1990","unstructured":"Matou\u0161ek, J.: Bi-lipschitz embeddings into low dimensional euclidean spaces. Comment. Math. Univ. Carolinae\u00a031(3), 589\u2013600 (1990)","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"21_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer, Heidelberg (2002)"},{"key":"21_CR30","doi-asserted-by":"crossref","unstructured":"Rabinovich, Y.: On average distortion of embedding metrics into l1 and into the line. In: 35th Annual ACM STOC (2003)","DOI":"10.1145\/780542.780609"},{"key":"21_CR31","doi-asserted-by":"crossref","unstructured":"Rabinovich, Y., Raz, R.: Lower bounds on the distortion of embedding finite metric spaces in graphs. GEOMETRY: Discrete & Computational Geometry\u00a019 (1998)","DOI":"10.1007\/PL00009336"},{"key":"21_CR32","unstructured":"Rao, S., Richa, A.: New approximation techniques for some ordering problems. In: SODA (1998)"},{"key":"21_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/3-540-47867-1_17","volume-title":"Integer Programming and Combinatorial Optimization","author":"R.A. Sitters","year":"2002","unstructured":"Sitters, R.A.: The minimum latency problem is np-hard for weighted trees. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 230\u2013239. Springer, Heidelberg (2002)"},{"issue":"1","key":"21_CR34","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1137\/0601008","volume":"1","author":"R.T. Wong","year":"1980","unstructured":"Wong, R.T.: Worst-case analysis of network design problem heuristics. SIAM Journal Alg. Disc. Math.\u00a01(1), 51\u201363 (1980)","journal-title":"SIAM Journal Alg. Disc. Math."}],"container-title":["Lecture Notes in Computer Science","STACS 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24749-4_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T17:08:49Z","timestamp":1740503329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24749-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212362","9783540247494"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24749-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}