Yair Bartal - Selected Publications
Embedding of Metric Spaces and Applications
-
Probabilistic Approximation of Metric Spaces
and its Algorithmic Applications
Y. Bartal.
In Proc. of the 37th Ann. IEEE Symp. on
Foundations of Computer Science, October 1996.
-
On Approximating Arbitrary Metrics by Tree Metrics
Y. Bartal.
In Proc. of the 30th Ann. ACM Symp. on
Theory of Computing, May 1998.
-
Graph Decomposition Lemmas and their Role in Metric Embedding Methods
Y. Bartal.
In
Proc. of the 6th Ann.
the European Symp. on Algorithms, September 2004.
-
Advances in Metric Embedding Theory
I. Abraham, Y. Bartal and O. Neiman.
In Proc. of the 38th Ann. ACM Symp. on
Theory of Computing, May 2006.
-
Embedding Metric Spaces in their Intrinsic Dimension
I. Abraham, Y. Bartal and O. Neiman.
In Proc. of the 19th ACM-SIAM Symp.
on Discrete Algorithms, January 2008.
-
Local Embeddings of Metric Spaces
I. Abraham, Y. Bartal and O. Neiman.
In Proc. of the 39th Ann. ACM Symp. on
Theory of Computing, June 2007.
-
Dimensionality Reduction: beyond the Johnson-Lindenstrauss bound
Y. Bartal, B. Recht and L. Schulman.
March 2010 (first version: October 2007).
-
Nearly Tight Low Stretch Spanning Trees
I. Abraham, Y. Bartal and O. Neiman.
In Proc. of the 49th IEEE Symp. on Foundations of Computer Science, October 2008.
-
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Contant Average Distortion
I. Abraham, Y. Bartal and O. Neiman.
In Proc. of the 18th ACM-SIAM Symp.
on Discrete Algorithms, January 2007.
-
Metric Embeddings with Relaxed Guarantees
I. Abraham, Y. Bartal, T-H. Chan, K. Dhamdhere, A. Gupta, J. Kleinberg, O. Neiman and A. Slivkins.
In Proc. of the 46th IEEE Symp. on Foundations of Computer Science, October 2005.
-
On Metric Ramsey-Type Phenomena
: Journal Version
(math audience).
Y. Bartal, N. Linial, M. Mendel and A. Naor.
In Annals of Mathematics, 2006.
-
On Metric Ramsey-Type Phenomena
: Conference Version
(CS audience).
Y. Bartal, N. Linial, M. Mendel and A. Naor.
In Proc. of the 35th Ann. ACM Symp. on
Theory of Computing, June 2003.
-
Ramsey-type Theorems for Metric Spaces with Applications
Y. Bartal, B. Bollobas, and M. Mendel.
In Proc. of the 42nd Ann. IEEE Symp. on
Foundations of Computer Science, October 2001.
-
Multi-Embedding and Path Approximation of Metric Spaces.
Y. Bartal and M. Mendel.
In Proc. of the 14th ACM-SIAM Symp.
on Discrete Algorithms, January 2003.
-
Dimension Reduction for Ultrametrics.
Y. Bartal and M. Mendel.
In Proc. of the 15th ACM-SIAM Symp.
on Discrete Algorithms, January 2004.
Algorithms
-
New Algorithms for an Ancient Scheduling Problem
Y. Bartal, A. Fiat, H. Karloff, and R. Vohra.
In Proc. of the 24th Ann. ACM Symp. on
Theory of Computing, May 1992.
-
A polylog(n)-Competitive Algorithm for Metrical Task Systems
Y. Bartal, A. Blum, C. Burch, and A. Tomkins.
In Proc. of the 29th Ann. ACM Symp. on Theory of Computing,
May 1997.
-
Approximating Min-Sum Clustering in Metric Spaces
Y. Bartal, M. Charikar, and D. Raz.
In Proc. of the 33rd Ann. ACM Symp. on Theory of Computing,
July 2001.
-
Global Optimization using Local Information with Applications
to Flow Control
Y. Bartal, J. Byers and D. Raz.
In Proc. of the 38th Ann. IEEE Symp. on
Foundations of Computer Science, October 1997.
-
The Harmonic k-Server Algorithm is Competitive
Y. Bartal and E. Grove.
In the JACM, 1994.
-
Survey on Distributed Paging
Y. Bartal.
Chapter in Book by A. Fiat and G, Woeginger, published as
Proc. of the Dagstul Workshop on On-line Algorithms,
July 1996.
-
Competitive Algorithms for Distributed Data Management
Y. Bartal, A. Fiat, and Y. Rabani.
In Proc. of the 24th Ann. ACM Symp. on Theory of Computing,
May 1992.
-
Heat & Dump: Competitive Distributed Paging
B. Awerbuch, Y. Bartal, and A. Fiat.
In Proc. of the 34th Ann. IEEE Symp. on Foundations of Computer Science,
October 1993.
Issues in Computational Economics
Yair Bartal
, E-mail: yair@cs.huji.ac.il