Yair Bartal  Publications
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.

On Embedding of Finite Metric Spaces into Hilbert Space
I. Abraham, Y. Bartal and O. Neiman.
Tech. Rerport, 2005.

Embedding Metric Spaces in their Intrinsic Dimension
I. Abraham, Y. Bartal and O. Neiman.
In Proc. of the 19th ACMSIAM 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.

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.

Dimensionality Reduction: beyond the JohnsonLindenstrauss bound
Y. Bartal, B. Recht and L. Schulman.
March 2010 (first version: October 2007).

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 ACMSIAM Symp.
on Discrete Algorithms, January 2007.

Metric Embeddings with Relaxed Guarantees
I. Abraham, Y. Bartal, TH. 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 Low Dimensional Local Embeddings
I. Abraham, Y. Bartal and O. Neiman.
In Proc. of the 20th ACMSIAM Symp.
on Discrete Algorithms, January 2009.

MultiEmbedding and Path Approximation of Metric Spaces.
Y. Bartal and M. Mendel.
In Proc. of the 14th ACMSIAM Symp.
on Discrete Algorithms, January 2003.

Ramseytype 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.

On Metric RamseyType Phenomena
: Journal Version
(math audience).
Y. Bartal, N. Linial, M. Mendel and A. Naor.
In Annals of Mathematics, 2005.

On Metric RamseyType 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.

On Some Low Distortion Metric Ramseytype Problems.
Y. Bartal, N. Linial, M. Mendel and A. Naor.
Accepted to Discrete and Computational Geometry, 2003.

On Lipschitz Embeddings of Ultrametrics in Low Dimention.
Y. Bartal, N. Linial, M. Mendel and A. Naor.
Accepted to European Journal on Combinatorics, 2003.

On Metric Ramseytype Dichotomies.
Y. Bartal, N. Linial, M. Mendel and A. Naor.
Submitted, 2003.

Limitations to Frechet Embedding of Metric Spaces.
Y. Bartal, N. Linial, M. Mendel and A. Naor.
Submitted, 2003.

Dimension Reduction for Ultrametrics.
Y. Bartal and M. Mendel.
In Proc. of the 15th ACMSIAM Symp.
on Discrete Algorithms, January 2004.

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 MinSum 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.

Randomized Algorithms for the kServer Problem in Growth Rate Bounded Metric Spaces.
Y. Bartal and M. Mendel.
In Proc. of the 15th ACMSIAM Symp. on Discrete Algorithms, January 2004.
 Issues in Computational Economics

NegotiationRange Mechanisms: Exploring the Limits of Truthful Efficient Markets.
Y. Bartal, R. Gonen and P. La Mura.
In Proc. of the 5th ACM Conf. on Electronic Commerce, May 2004.

Incentive Compatible MultiUnit Combinatorial Auctions.
Y. Bartal, R. Gonen and N. Nisan.
In Proc. Theoretical Aspect of Rationality and Knowledge, June 2003.

On Capital Investment
Y. Azar, Y. Bartal, E. Feuerstein, A. Fiat,
S. Leonardi, and A. Rosen.
In Proc. of the 23rd International Collequium on Automata,
Languages, and Programming.,
July 1996.
 Algorithmic issues in Networking

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.

A Modular Analysis of Network Transmission Protocols
M. Adler, Y. Bartal, J. Byers, M. Luby and D. Raz.
In Proc. of the 5th Israeli Symp.
on Theory of Computing and Systems,
June 1997.

FeedbackFree Multicast Prefix Protocols
Y. Bartal, J. Byers, M. Luby and D. Raz.
In Proc. of the 3rd IEEE Symp. on Computers and Communication.
June 1998.

Fast, Fair and Frugal Bandwidth Allocation in ATM Networks
Y. Bartal, M. FarachColton, S. Yooseph, and L. Zhang.
In Proc. of the 10th Ann. ACMSIAM Symp. on Discrete Algorithms,
January 1999.

A Generic Scheme for Building Overlay Networks in Adversarial Scenarios
I. Abraham, B. Awerbuch, Y. Azar, Y. Bartal, D. Malkhi,
and E. Pavlov.
In Proc. of IPDPS, April 2003.
 Scheduling

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 Better Lower Bound for OnLine Scheduling
Y. Bartal, H. Karloff, and Y. Rabani.
In Information Processing Letters 50 (1994), 113116.

Minimizing Maximum Response Time in Scheduling Broadcasts
Y. Bartal and M. Muthukrishnan.
In Proc. of the 11th Ann. ACMSIAM Symp. on Discrete Algorithms,
January 2000.

Multiprocessor Scheduling with Rejection
Y. Bartal, S. Leonardi, A. MarchettiSpaccamela,
J. Sgall, and L. Stougie.
In Proc. of the 7th Ann. ACMSIAM Symp. on Discrete Algorithms,
January 1996.

Online Algorithms for Maximizing Weighted Throughput of Unit Jobs
Y. Bartal, F.Y.L Chin, M. Chrobak, S.P.Y. Fung, W. Jawor, R. Lavi, J. Sgall,
and T. Tichy.
In Proc. of STACS 2004.

On the Value of Preemption in Scheduling
Y. Bartal, S. Leonardi, G. Shallom, and R. Sitters.
In Proc. of APPROX 2006.
 Metrical Task Systems and Servers

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.

Ramseytype 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.

Randomized Algorithms for the kServer Problem in Growth Rate Bounded
Metric Spaces.
Y. Bartal and M. Mendel.
In Proc. of the 15th ACMSIAM Symp.
on Discrete Algorithms, January 2004.

The Harmonic kServer Algorithm is Competitive
Y. Bartal and E. Grove.
In the JACM, 1994.

A Randomized Algorithm for Two Servers on the Line
Y. Bartal, M. Chrobak and L. Larmore.
In Proc. of the 6th Ann. European Symp. on Algorithms, August 1998.

On the Competitive Ratio of the Work Function Algorithm for the kServer Problem
Y. Bartal and E. Koutsoupias.
In Proc. of the 17th Ann. Stmp. on Theoretical Aspects of Computer
Sience, pages 605613, 2000.

On Page Migration and Other Relaxed Task Systems
Y. Bartal, M. Charikar and P. Indyk.
In Proc. of the 8th Ann. ACMSIAM Symp. on Discrete Algorithms,
January 1997.

The Distributed kServer Problem 
A Competitive Distributed Translator for kServer Algorithms
Y. Bartal and A. Rosen.
In Proc. of the 33rd Ann. IEEE Symp. on Foundations of Computer Science,
October 1992.

More on Random Walks, Electrical Networks, and the
Harmonic Random Walk
Y. Bartal, M. Chrobak, J. Noga, and P. Raghavan.
Submitted to IPL, November 2001.
 Routing, Flow, and Admission Control

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.

Competitive NonPreemptive CallControl
B. Awerbuch, Y. Bartal, A. Fiat, and A. Rosen.
In Proc. of the 5th Ann. ACMSIAM Symp. on Discrete Algorithms,
January 1994.

Lower Bounds for Online Graph Problems
with Applications to Circuit and Optical Routing
Y. Bartal, A. Fiat, and S. Leonardi.
In Proc. of the 28th Ann. ACM Symp. on Theory of Computing,
May 1996.

OnLine Routing in AllOptical Networks
Y. Bartal and S. Leonardi.
In Proc. of the 24th International Collequium on Automata,
Languages, and Programming.,
July 1997.

Fast, Fair and Frugal Bandwidth Allocation in ATM Networks
Y. Bartal, M. FarachColton, S. Yooseph, and L. Zhang.
In Proc. of the 10th Ann. ACMSIAM Symp. on Discrete Algorithms,
January 1999.
 Distributed Paging

Survey on Distributed Paging
Y. Bartal.
Chapter in Book by A. Fiat and G, Woeginger, published as
Proc. of the Dagstul Workshop on Online 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.

Competitive Distributed File Allocation
B. Awerbuch, Y. Bartal, and A. Fiat.
In Proc. of the 25th Ann. ACM Symp. on Theory of Computing,
May 1993.

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.

Distribued Paging for General Networks
B. Awerbuch, Y. Bartal, and A. Fiat.
In Proc. of the 7th Ann. ACMSIAM Symp. on Discrete Algorithms,
January 1996.

On Page Migration and Other Relaxed Task Systems
Y. Bartal, M. Charikar and P. Indyk.
In Proc. of the 8th Ann. ACMSIAM Symp. on Discrete Algorithms,
January 1997.
 Clustering
 Network Design
 Security
 Databases
Yair Bartal
, Email: yair@cs.huji.ac.il