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 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.
    
  • 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 Johnson-Lindenstrauss 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 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 Low Dimensional Local Embeddings
    I. Abraham, Y. Bartal and O. Neiman.
    In Proc. of the 20th ACM-SIAM Symp. on Discrete Algorithms, January 2009.
    
  • 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.
    
  • 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.
    
  • On Metric Ramsey-Type Phenomena : Journal Version (math audience).
    Y. Bartal, N. Linial, M. Mendel and A. Naor.
    In Annals of Mathematics, 2005.
    
  • 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.
    
  • On Some Low Distortion Metric Ramsey-type 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 Ramsey-type 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 ACM-SIAM 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 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.
    
  • Randomized Algorithms for the k-Server Problem in Growth Rate Bounded Metric Spaces.
    Y. Bartal and M. Mendel.
    In Proc. of the 15th ACM-SIAM Symp. on Discrete Algorithms, January 2004.
  
  
• Issues in Computational Economics
  
  
  • Negotiation-Range 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 Multi-Unit 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.
    
  • Feedback-Free 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. Farach-Colton, S. Yooseph, and L. Zhang.
    In Proc. of the 10th Ann. ACM-SIAM 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 On-Line Scheduling
    Y. Bartal, H. Karloff, and Y. Rabani.
    In Information Processing Letters 50 (1994), 113-116.
    
  • Minimizing Maximum Response Time in Scheduling Broadcasts
    Y. Bartal and M. Muthukrishnan.
    In Proc. of the 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2000.
    
  • Multiprocessor Scheduling with Rejection
    Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, and L. Stougie.
    In Proc. of the 7th Ann. ACM-SIAM 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.
    
  • 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.
    
  • Randomized Algorithms for the k-Server Problem in Growth Rate Bounded Metric Spaces.
    Y. Bartal and M. Mendel.
    In Proc. of the 15th ACM-SIAM Symp. on Discrete Algorithms, January 2004.
    
  • The Harmonic k-Server 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 k-Server Problem
    Y. Bartal and E. Koutsoupias.
    In Proc. of the 17th Ann. Stmp. on Theoretical Aspects of Computer Sience, pages 605-613, 2000.
    
  • On Page Migration and Other Relaxed Task Systems
    Y. Bartal, M. Charikar and P. Indyk.
    In Proc. of the 8th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 1997.
    
  • The Distributed k-Server Problem --- A Competitive Distributed Translator for k-Server 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 Non-Preemptive Call-Control
    B. Awerbuch, Y. Bartal, A. Fiat, and A. Rosen.
    In Proc. of the 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 1994.
    
  • Lower Bounds for On-line 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.
    
  • On-Line Routing in All-Optical 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. Farach-Colton, S. Yooseph, and L. Zhang.
    In Proc. of the 10th Ann. ACM-SIAM 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 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.
    
  • 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. ACM-SIAM 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. ACM-SIAM Symp. on Discrete Algorithms, January 1997.
  
  
• Clustering
  • 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.
  
  
• Network Design
  • On-line Generalized Steiner Problem
    B. Awerbuch, Y. Azar, and Y. Bartal.
    In Proc. of the 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 1996.
  
  
• Security
  
  
  • Firmato: A Novel Firewall Management Toolkit
    Y. Bartal, A. Mayer, K. Nissim and A. Wool.
    In Proc. IEEE Symp. on Security and Privacy, May 1999.
  
  
• Databases
  
  
  • AQUA: System and Techniques for Approximate Query Answeing
    P. Gibbos, V. Poosala, S. Acharya, Y. Bartal, Y. Matias, M. Muthukishnan, S. Ramaswamy, and T. Suel.
    In Bell Labs TR 1998.