On approximating arbitrary metrices by tree metrics

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AA97	B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
	AAB96	Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.68-74, January 28-30, 1996, Atlanta, Georgia, United States
	ABF93a	Baruch Awerbuch , Yair Bartal , Amos Fiat, Competitive distributed file allocation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.164-173, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167142]
	ABF93b	B. Awerbuch, Y. Bartal, and A. Fiat. Heat & Dump: Randomized competitive distributed paging. In Proc. 8drd IEEE Syrup. on Foundations of Computer Science, pages 22- 31,November 1993.
	ABF96	Baruch Awerbuch , Yair Bartal , Amos Fiat, Distributed paging for general networks, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.574-583, January 28-30, 1996, Atlanta, Georgia, United States
	ABFNPT96	Richa Agarwala , Vineet Bafna , Martin Farach , Babu Narayanan , Mike Paterson , Mikkel Thorup, On the approximability of numerical taxonomy (fitting distances by tree metrics), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.365-372, January 28-30, 1996, Atlanta, Georgia, United States
	ABLP89	B. Awerbuch , A. Bar-Noy , N. Linial , D. Peleg, Compact distributed data structures for adaptive routing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.479-489, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73053]
	ADDJS90	Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
	AKPW91	Noga Alon , Richard M. Karp , David Peleg , Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem, SIAM Journal on Computing, v.24 n.1, p.78-100, Feb. 1995 [doi>10.1137/S0097539792224474]
	AP90	B. Awerbuch and D. Peleg. Sparse partitions. In Prec. 316t IEEE Syrup. on Foundations of Computer Science, pages 503-513, 1990.
	AP91	Baruch Awerbuch , David Peleg, Concurrent online tracking of mobile users, Proceedings of the conference on Communications architecture & protocols, p.221-233, September 03-06, 1991, Zurich, Switzerland
	AS98	Topology Aggregation for Directed Graph, Proceedings of the Third IEEE Symposium on Computers & Communications, p.47, June 30-July 02, 1998
	Bart96	Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
	Bour85	J. Bourgain. On Lipshitz Embedding of Finite Metric Spaces in Hilbert Space. In Israel J. Afath. 52, pages 46-52, 1985.
	BBKTW90	S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
	BBBT97	Yair Bartal , Avrim Blum , Carl Burch , Andrew Tomkins, A polylog(n)-competitive algorithm for metrical task systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.711-719, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258667]
	BFR92	Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.39-50, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129717]
	BG92	J-P. Barthdemy and A. Gu6noche. Trees and Proximity Representations. Wiles; New York, 1991.
	BLS87	A. Borodin , N. Linial , M. Saks, An optimal online algorithm for metrical task systems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.373-382, January 1987, New York, New York, United States [doi>10.1145/28395.28435]
	BR92	Y. Bartal and A. Ros~n. The Distributed k-Server Problem -- A Competitive Distributed Translator for k-Server Algorithms. In Prec. of the 33rd Ann. IEEE Syrup. on Foundations of Computer Science, pages 34,1-353, October 1992.
	Cai92	L. Cat. Tree Spanners: Spanning trees that Appi-oximate Distances. Ph.D Thesis. Tech. Report 260}92, Univ. of Toronto, May 1992.
	CC95	Leizhen Cai , Derek G. Corneil, Tree Spanners, SIAM Journal on Discrete Mathematics, v.8 n.3, p.359-387, Aug. 1995 [doi>10.1137/S0895480192237403]
	CCGG98	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276719]
	CCGGP98	M. Charit~r, C. Chekuri, A. Goel, S. Guha, and S. Plotkin. Approximating an Arbitrary Metric by O(r~l~,gn) 'Ire :~. Personal communication.
	CDNS92	Barun Chandra , Gautam Das , Giri Narasimhan , Jose Soares, New Sparseness Results on Graph Spanners, University of Chicago, Chicago, IL, 1992
	CL91	Marek Chrobak , Lawrence L. Larmore, An optimal on-line algorithm for K-servers on trees, SIAM Journal on Computing, v.20 n.1, p.144-148, Feb. 1991 [doi>10.1137/0220008]
	ENRS95	G. Even , J. Naor , S. Rao , B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.62, October 23-25, 1995
	GKR98	Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
	GW85	R.L. Graham and P.M. Winkler. On Isometric Embeddings of Graphs. In Trans. of the Amer. Math. See. 288, pages 527-536, 1985.
	Hu74	T.C. Hu. Optimum Communication Spanning Trees. In SIAM J. Computing, vol. 3, pages 188-195, 197,1.
	JL84	W.B. Johnson and J. Lindenstrauss. Extensions of of Lipschitz Mappings into a Hilbert Space. in Contemporary Mathemetics 26, pages 189-206, 1984.
	Karp89	R.M. Karp. A 2k-competitive Algorithm for the Circle. Manuscript, August 1989.
	KH97	O. Kariv and S.L. Haldmi. An Algorithmic Approach to Network Location Problems, Part Ih p-Medians. In SIAM J. Appl. Math., 37:539-560, 1979.
	KP94	Elias Koutsoupias , Christos Papadimitriou, On the k-server conjecture, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.507-511, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195245]
	KRS98	G. Konjevod, R. Ravi, and F.$. Salman. On Approximating Planar Metrics by Tree Metrics. Manuscript.
	LLR94	N. Lintel, E. London, and Y. Rabinovich. The Geometry of Graphs and Some of its Algorithmic Applications. In Prec. of the 35th Ann. IEEE Symp. on Foundations of Computer Science, pages 577-591, October 1994.
	LS91	Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States
	MMS88	Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62243]
	Neum59	Zur Theorie der Gesellsehaftsspiele. Math. Ann., 100:295-320, 1928. Translation: On the Theory of Games of Strategy. Contribution to the Theory of Games, voh 4~ ed. by A.W. Tucker and R.D. Luce, Princeton Univ. Press 1959.
	PS89	D. Peleg and A.A. Sch~iffer. Graph Spanners. In Journal of Graph Theory, 13(1):99-106, 1989.
	PU89	David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, SIAM Journal on Computing, v.18 n.4, p.740-747, Aug. 1989 [doi>10.1137/0218050]
	RR95	Y. Rabinovich and R. Raz. Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. To appear in Discrete and Computational Geometry.
	Seym95	P.D. Seymour. Packing Directed Circuits Fractlonall}: In Combinatorica, 15(2):281-288, 1995.
	ST85	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	Tami96	A. Tamir. An O(pn2) Algorithm for the p-Median and Related Problems on Tree Graphs. In Operations Research Letters, 19:59-64, 1996.
	WLBCRT98	Bang Ye Wu , Giuseppe Lancia , Vineet Bafna , Kun-Mao Chao , R. Ravi , Chuan Yi Tang, A polynomial time approximation scheme for minimum routing cost spanning trees, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.21-32, January 25-27, 1998, San Francisco, California, United States