Yair Bartal

According to our database1, Yair Bartal authored at least 74 papers between 1992 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2019
Approximate nearest neighbor search for p-spaces (2 (DOI)
Theor. Comput. Sci., 2019

Covering Metric Spaces by Few Trees.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Approximate Nearest Neighbor Search for \ell _p -Spaces (2 via Embeddings.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2016
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Dimension Reduction Techniques for ℓp (1 (DOI)
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp.
SIAM J. Discrete Math., 2015

2014
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013
A Linear Time Approximation Scheme for Euclidean TSP.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011
Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Fast, precise and dynamic distance queries.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Bandwidth and Low Dimensional Embedding.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Volume in General Metric Spaces.
Proceedings of the Algorithms, 2010

2009
Universal Immersion Spaces for Edge-Colored Graphs and Nearest-Neighbor Metrics.
SIAM J. Discrete Math., 2009

On low dimensional local embeddings.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Embedding metric spaces in their intrinsic dimension.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Nearly Tight Low Stretch Spanning Trees.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Local embeddings of metric spaces.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Ramsey-type theorems for metric spaces with applications to online problems.
J. Comput. Syst. Sci., 2006

Advances in metric embedding theory.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

On the Value of Preemption in Scheduling.
Proceedings of the Approximation, 2006

2005
Randomized k-server algorithms for growth-rate bounded graphs.
J. Algorithms, 2005

Some Low Distortion Metric Ramsey Problems.
Discrete & Computational Geometry, 2005

Metric Embeddings with Relaxed Guarantees.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Firmato: A novel firewall management toolkit.
ACM Trans. Comput. Syst., 2004

Multiembedding of Metric Spaces.
SIAM J. Comput., 2004

Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control.
SIAM J. Comput., 2004

Low dimensional embeddings of ultrametrics.
Eur. J. Comb., 2004

Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs.
Proceedings of the STACS 2004, 2004

Randomized k-server algorithms for growth-rate bounded graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Dimension reduction for ultrametrics.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Negotiation-range mechanisms: exploring the limits of truthful efficient markets.
Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

Graph Decomposition Lemmas and Their Role in Metric Embedding Methods.
Proceedings of the Algorithms, 2004

2003
Incentive compatible multi unit combinatorial auctions.
Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2003), 2003

On metric ramsey-type phenomena.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Multi-embedding and path approximation of metric spaces.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

A Generic Scheme for Building Overlay Networks in Adversarial Scenarios.
Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 2003

2002
More on random walks, electrical networks, and the harmonic k-server algorithm.
Inf. Process. Lett., 2002

Fast, Fair and Frugal Bandwidth Allocation in ATM Networks.
Algorithmica, 2002

2001
On page migration and other relaxed task systems.
Theor. Comput. Sci., 2001

Approximating min-sum k-clustering in metric spaces.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
The harmonic k-server algorithm is competitive.
J. ACM, 2000

A Randomized Algorithm for Two Servers on the Line.
Inf. Comput., 2000

On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem.
Proceedings of the STACS 2000, 2000

Minimizing maximum response time in scheduling broadcasts.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
Firmato: A Novel Firewall Management Toolkit.
Proceedings of the 1999 IEEE Symposium on Security and Privacy, 1999

Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
On Approximating Arbitrary Metrices by Tree Metrics.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Feedback-free multicast prefix protocols.
Proceedings of the Third IEEE Symposium on Computers and Communications (ISCC 1998), June 30, 1998

A Randomized Algorithm for Two Servers on the Line (Extended Abstract).
Proceedings of the Algorithms, 1998

1997
The Distributed k-Server Problem - A Competitive Distributed Translator for k-Server Algorithms.
J. Algorithms, 1997

A polylog(n)-Competitive Algorithm for Metrical Task Systems.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

On Page Migration and Other Related Task Systems.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

A Modular Analysis of Network Transmission Protocols.
Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

On-Line Routing in All-Optical Networks.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Global Optimization Using Local Information with Applications to Flow Control.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Multiprocessor Scheduling with Rejection.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Distributed Paging for General Networks.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On-line Generalized Steiner Problem.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On Capital Investment.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Distributed Paging.
Proceedings of the Online Algorithms, 1996

1995
Competitive Algorithms for Distributed Data Management.
J. Comput. Syst. Sci., 1995

New Algorithms for an Ancient Scheduling Problem.
J. Comput. Syst. Sci., 1995

1994
A Better Lower Bound for On-Line Scheduling.
Inf. Process. Lett., 1994

Competitive Non-Preemptive Call Control.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
Competitive distributed file allocation.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Heat & Dump: Competitive Distributed Paging
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Competitive Algorithms for Distributed Data Management (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

New Algorithms for an Ancient Scheduling Problem
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992


  Loading...