Yair Bartal

111 papers A* 47A 5B 2C 1Journal 49Unranked 6
YearRankTypeTitle / Venue / Authors
2025 A* conf
Improved Fixed-Parameter Bounds for Min-Sum-Radii and Diameters k-Clustering and Their Fair Variants.
AAAI
Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, Alon Hovav
2025 J jnl
Improved fixed-parameter bounds for Min-Sum-Radii and Diameters
CoRR
Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, Alon Hovav
2024 A* conf
Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications.
FOCS
Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb, Alon Hovav
2024 J jnl
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds.
CoRR
Yair Bartal, Ora Nova Fandina, Seeun William Umboh
2022 J jnl
Covering metric spaces by few trees.
J. Comput. Syst. Sci.
Yair Bartal, Ora Nova Fandina, Ofer Neiman
2022 A* conf
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures.
SoCG
Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
2021 J jnl
Advances in Metric Ramsey Theory and its Applications.
CoRR
Yair Bartal
2021 A* conf
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces.
STOC
Yair Bartal, Lee-Ad Gottlieb
2021 J jnl
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures.
CoRR
Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
2020 A* conf
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds.
SODA
Yair Bartal, Nova Fandina, Seeun William Umboh
2019 J jnl
Approximate nearest neighbor search for
Theor. Comput. Sci.
Yair Bartal, Lee-Ad Gottlieb
2019 A* conf
Covering Metric Spaces by Few Trees.
ICALP
Yair Bartal, Nova Fandina, Ofer Neiman
2019 J jnl
Covering Metric Spaces by Few Trees.
CoRR
Yair Bartal, Nova Fandina, Ofer Neiman
2019 A* conf
Dimensionality reduction: theoretical perspective on practical measures.
NeurIPS
Yair Bartal, Nova Fandina, Ofer Neiman
2019 J jnl
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces.
CoRR
Lee-Ad Gottlieb, Yair Bartal
2019 J jnl
On notions of distortion and an almost minimum spanning tree with constant average distortion.
J. Comput. Syst. Sci.
Yair Bartal, Arnold Filtser, Ofer Neiman
2018 B conf
Approximate Nearest Neighbor Search for \ell _p -Spaces (2 via Embeddings.
LATIN
Yair Bartal, Lee-Ad Gottlieb
2016 A* conf
Dimension Reduction Techniques for ℓ
SoCG
Yair Bartal, Lee-Ad Gottlieb
2016 A* conf
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion.
SODA
Yair Bartal, Arnold Filtser, Ofer Neiman
2016 J jnl
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion.
CoRR
Yair Bartal, Arnold Filtser, Ofer Neiman
2016 J jnl
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme.
SIAM J. Comput.
Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
2015 J jnl
Approximate nearest neighbor search for ℓ
CoRR
Yair Bartal, Lee-Ad Gottlieb
2015 J jnl
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion.
SIAM J. Comput.
Ittai Abraham, Yair Bartal, Ofer Neiman
2015 J jnl
Local Embeddings of Metric Spaces.
Algorithmica
Ittai Abraham, Yair Bartal, Ofer Neiman
2015 J jnl
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓ
SIAM J. Discret. Math.
Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman
2014 J jnl
Dimension reduction techniques for ℓ
CoRR
Yair Bartal, Lee-Ad Gottlieb
2014 A* conf
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp.
SoCG
Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman
2014 J jnl
Volume in General Metric Spaces.
Discret. Comput. Geom.
Ittai Abraham, Yair Bartal, Ofer Neiman, Leonard J. Schulman
2013 A* conf
A Linear Time Approximation Scheme for Euclidean TSP.
FOCS
Yair Bartal, Lee-Ad Gottlieb
2013 J jnl
Bandwidth and low dimensional embedding.
Theor. Comput. Sci.
Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman
2013 J jnl
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓ
CoRR
Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman
2012 A* conf
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme.
STOC
Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
2011 — conf
Bandwidth and Low Dimensional Embedding.
APPROX-RANDOM
Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman
2011 A* conf
Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound.
SODA
Yair Bartal, Ben Recht, Leonard J. Schulman
2011 A* conf
Fast, precise and dynamic distance queries.
SODA
Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty
2011 J jnl
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
CoRR
Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
2010 J jnl
Fast, precise and dynamic distance queries
CoRR
Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty
2010 — conf
Volume in General Metric Spaces.
ESA (2)
Ittai Abraham, Yair Bartal, Ofer Neiman, Leonard J. Schulman
2009 A* conf
On low dimensional local embeddings.
SODA
Ittai Abraham, Yair Bartal, Ofer Neiman
2009 J jnl
Universal Immersion Spaces for Edge-Colored Graphs and Nearest-Neighbor Metrics.
SIAM J. Discret. Math.
Yair Bartal, Leonard J. Schulman
2008 A* conf
Embedding metric spaces in their intrinsic dimension.
SODA
Ittai Abraham, Yair Bartal, Ofer Neiman
2008 J jnl
Nearly Tight Low Stretch Spanning Trees
CoRR
Ittai Abraham, Yair Bartal, Ofer Neiman
2008 A* conf
Nearly Tight Low Stretch Spanning Trees.
FOCS
Ittai Abraham, Yair Bartal, Ofer Neiman
2007 A* conf
Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion.
SODA
Ittai Abraham, Yair Bartal, Ofer Neiman
2007 A* conf
Local embeddings of metric spaces.
STOC
Ittai Abraham, Yair Bartal, Ofer Neiman
2006 A* conf
Advances in metric embedding theory.
STOC
Ittai Abraham, Yair Bartal, Ofer Neiman
2006 J jnl
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
CoRR
Ittai Abraham, Yair Bartal, Ofer Neiman
2006 J jnl
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing.
SIAM J. Comput.
Yair Bartal, Amos Fiat, Stefano Leonardi
2006 — conf
On the Value of Preemption in Scheduling.
APPROX-RANDOM
Yair Bartal, Stefano Leonardi, Gil Shallom, René Sitters
2006 J jnl
Ramsey-type theorems for metric spaces with applications to online problems.
J. Comput. Syst. Sci.
Yair Bartal, Béla Bollobás, Manor Mendel
2005 A* conf
Metric Embeddings with Relaxed Guarantees.
FOCS
Ittai Abraham, Yair Bartal, T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Ofer Neiman, Aleksandrs Slivkins
2005 J jnl
Randomized k-server algorithms for growth-rate bounded graphs.
J. Algorithms
Yair Bartal, Manor Mendel
2005 J jnl
Some Low Distortion Metric Ramsey Problems.
Discret. Comput. Geom.
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
2004 A* conf
Dimension reduction for ultrametrics.
SODA
Yair Bartal, Manor Mendel
2004 J jnl
Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control.
SIAM J. Comput.
Yair Bartal, John W. Byers, Danny Raz
2004 A conf
Graph Decomposition Lemmas and Their Role in Metric Embedding Methods.
ESA
Yair Bartal
2004 J jnl
Low dimensional embeddings of ultrametrics.
Eur. J. Comb.
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
2004 J jnl
Multi-Embedding of Metric Spaces
CoRR
Yair Bartal, Manor Mendel
2004 J jnl
Multiembedding of Metric Spaces.
SIAM J. Comput.
Yair Bartal, Manor Mendel
2004 A* conf
Negotiation-range mechanisms: exploring the limits of truthful efficient markets.
EC
Yair Bartal, Rica Gonen, Pierfrancesco La Mura
2004 J jnl
On the competitive ratio of the work function algorithm for the k-server problem.
Theor. Comput. Sci.
Yair Bartal, Elias Koutsoupias
2004 J jnl
On-line generalized Steiner problem.
Theor. Comput. Sci.
Baruch Awerbuch, Yossi Azar, Yair Bartal
2004 A conf
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs.
STACS
Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jirí Sgall, Tomás Tichý
2004 J jnl
Ramsey-type theorems for metric spaces with applications to online problems
CoRR
Yair Bartal, Béla Bollobás, Manor Mendel
2004 A* conf
Randomized
SODA
Yair Bartal, Manor Mendel
2003 A conf
A Generic Scheme for Building Overlay Networks in Adversarial Scenarios.
IPDPS
Ittai Abraham, Baruch Awerbuch, Yossi Azar, Yair Bartal, Dahlia Malkhi, Elan Pavlov
2003 J jnl
Competitive distributed file allocation.
Inf. Comput.
Baruch Awerbuch, Yair Bartal, Amos Fiat
2003 B conf
Incentive compatible multi unit combinatorial auctions.
TARK
Yair Bartal, Rica Gonen, Noam Nisan
2003 A* conf
Multi-embedding and path approximation of metric spaces.
SODA
Yair Bartal, Manor Mendel
2003 A* conf
On metric ramsey-type phenomena.
STOC
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
2002 J jnl
Fast, Fair and Frugal Bandwidth Allocation in ATM Networks.
Algorithmica
Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang
2002 J jnl
More on random walks, electrical networks, and the harmonic k-server algorithm.
Inf. Process. Lett.
Yair Bartal, Marek Chrobak, John Noga, Prabhakar Raghavan
2001 A* conf
A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems.
FOCS
Yair Bartal, Béla Bollobás, Manor Mendel
2001 A* conf
Approximating min-sum
STOC
Yair Bartal, Moses Charikar, Danny Raz
2001 J jnl
On page migration and other relaxed task systems.
Theor. Comput. Sci.
Yair Bartal, Moses Charikar, Piotr Indyk
2000 J jnl
A Randomized Algorithm for Two Servers on the Line.
Inf. Comput.
Yair Bartal, Marek Chrobak, Lawrence L. Larmore
2000 A* conf
Minimizing maximum response time in scheduling broadcasts.
SODA
Yair Bartal, S. Muthukrishnan
2000 J jnl
Multiprocessor Scheduling with Rejection.
SIAM J. Discret. Math.
Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jirí Sgall, Leen Stougie
2000 A conf
On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem.
STACS
Yair Bartal, Elias Koutsoupias
2000 J jnl
The harmonic
J. ACM
Yair Bartal, Eddie Grove
1999 A* conf
Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks.
SODA
Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang
1999 — conf
Firmato: A Novel Firewall Management Toolkit.
S&P
Yair Bartal, Alain J. Mayer, Kobbi Nissim, Avishai Wool
1999 J jnl
On Capital Investment.
Algorithmica
Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén
1999 J jnl
On-Line Routing in All-Optical Networks.
Theor. Comput. Sci.
Yair Bartal, Stefano Leonardi
1998 A conf
A Randomized Algorithm for Two Servers on the Line (Extended Abstract).
ESA
Yair Bartal, Marek Chrobak, Lawrence L. Larmore
1998 J jnl
Distributed Paging for General Networks.
J. Algorithms
Baruch Awerbuch, Yair Bartal, Amos Fiat
1998 C conf
Feedback-free multicast prefix protocols.
ISCC
Yair Bartal, John W. Byers, Michael Luby, Danny Raz
1998 A* conf
On Approximating Arbitrary Metrices by Tree Metrics.
STOC
Yair Bartal
1997 — conf
A Modular Analysis of Network Transmission Protocols.
ISTCS
Micah Adler, Yair Bartal, John W. Byers, Michael Luby, Danny Raz
1997 A* conf
A polylog(
STOC
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
1997 A* conf
Global Optimization Using Local Information with Applications to Flow Control.
FOCS
Yair Bartal, John W. Byers, Danny Raz
1997 A* conf
On Page Migration and Other Relaxed Task Systems.
SODA
Yair Bartal, Moses Charikar, Piotr Indyk
1997 A* conf
On-Line Routing in All-Optical Networks.
ICALP
Yair Bartal, Stefano Leonardi
1997 J jnl
The Distributed k-Server Problem - A Competitive Distributed Translator for k-Server Algorithms.
J. Algorithms
Yair Bartal, Adi Rosén
1996 A* conf
Distributed Paging for General Networks.
SODA
Baruch Awerbuch, Yair Bartal, Amos Fiat
1996 — conf
Distributed Paging.
Online Algorithms
Yair Bartal
1996 A* conf
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing.
STOC
Yair Bartal, Amos Fiat, Stefano Leonardi
1996 A* conf
Multiprocessor Scheduling with Rejection.
SODA
Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jirí Sgall, Leen Stougie
1996 A* conf
On Capital Investment.
ICALP
Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén
1996 A* conf
On-line Generalized Steiner Problem.
SODA
Baruch Awerbuch, Yossi Azar, Yair Bartal
1996 A* conf
Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications.
FOCS
Yair Bartal
1995 J jnl
Competitive Algorithms for Distributed Data Management.
J. Comput. Syst. Sci.
Yair Bartal, Amos Fiat, Yuval Rabani
1995 J jnl
New Algorithms for an Ancient Scheduling Problem.
J. Comput. Syst. Sci.
Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra
1994 J jnl
A Better Lower Bound for On-Line Scheduling.
Inf. Process. Lett.
Yair Bartal, Howard J. Karloff, Yuval Rabani
1994 A* conf
Competitive Non-Preemptive Call Control.
SODA
Baruch Awerbuch, Yair Bartal, Amos Fiat, Adi Rosén
1994 — —
Competitive analysis of distributed on-line problems - distributed paging
Yair Bartal
1993 A* conf
Competitive distributed file allocation.
STOC
Baruch Awerbuch, Yair Bartal, Amos Fiat
1993 A* conf
Heat & Dump: Competitive Distributed Paging
FOCS
Baruch Awerbuch, Yair Bartal, Amos Fiat
1992 A* conf
Competitive Algorithms for Distributed Data Management (Extended Abstract)
STOC
Yair Bartal, Amos Fiat, Yuval Rabani
1992 A* conf
New Algorithms for an Ancient Scheduling Problem
STOC
Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra
1992 A* conf
The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms
FOCS
Yair Bartal, Adi Rosén