Universal immersion spaces for edge-colored graphs and nearest-neighbor metrics (2009)
Bartal, Yair, Schulman, Leonard J.
There exist finite universal immersion spaces for the following: (a) Edge-colored graphs of bounded degree and boundedly many colors. (b) Nearest-neighbor metrics of bounded degree and boundedly many...
A Nash-type Dimensionality Reduction for Discrete Subsets of L2 (2008)
Yair Bartal, Ben Recht, Leonard J. Schulman
Pursuing a line of work begun by Whitney, Nash showed that every C 1 manifold of dimension d can be embedded in R 2d+2 in such a manner that the local structure at each point is preserved...
Abstract Metric embeddings have become a frequent tool in the design of algorithms. The applicability is often dependent on how high the embedding's distortion is. For example embedding into...
Nearly Tight Low Stretch Spanning Trees (2008)
Abraham, Ittai, Bartal, Yair, Neiman, Ofer
We prove that any graph $G$ with $n$ points has a distribution $\mathcal{T}$ over spanning trees such that for any edge $(u,v)$ the expected stretch $E_{T \sim \mathcal{T}}[d_T(u,v)/d_G(u,v)]$ is...
Yair Bartal, Moses Charikar, Danny Raz
ABSTRACT The min-sum k-clustering problem in a metric space is to find a partition of the space into k clusters as to minimize the total sum of distances between pairs of points assigned to the same...
Yair Bartal, Moses Charikar, Danny Raz
ABSTRACT The min-sum k-clustering problem in a metric space is to find a partition of the space into k clusters as to minimize the total sum of distances between pairs of points assigned to the same...
This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file...
We present lower bounds on the competitive ratio of randomized algorithms for a wide class of on-line graph optimization problems and we apply such results to on-line virtual circuit and optical...
Yair Bartal, Stefano Leonardi, Alberto Marchetti-spaccamela, Leen Stougie
We consider a version of multiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. An instance of the problem is given by m identical parallel machines and a...
Yair Bartal, Moses Charikar, Piotr Indyk
This paper is concerned with the page migration (or file migration) problem [BS89] as part of a large class of on-line problems. The page migration problem deals with the management of pages residing...
Yossi Azar, Yair Bartal, Esteban Feuerstein, Stefano Leonardi
We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new...
We deal with randomized competitive algorithms for non-preemptive call control on tree-like switching networks. We give an O(log n) competitive algorithm for nonpreemptive call scheduling on trees....
Yair Bartal, Howard Karloff, Rakesh Vohra
We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the makespan, the...
We consider the k-server problem [23] in a distributed setting. Given a network of n processors, and k identical mobile servers, requests for service appear at the processors and a server must reach...
Baruch Awerbuch, Yossi Azar, Yair Bartal
The Generalized Steiner Problem (GSP) is defined as follows. We are given a graph with non-negative weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph such...
On-line Algorithms for Generalized Steiner Tree and Network Connectivity Leasing (2007)
Baruch Awerbuch, Yossi Azar, Yair Bartal
The Generalized Steiner Tree (GST) problem is defined as follows. We are given a graph with non-negative weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph...
Competitive Distributed File Allocation (Extended Abstract) (2007)
Baruch Awerbuch, Yair Bartal, Amos Fiat
) Baruch Awerbuch Yair Bartal y Amos Fiat y Abstract This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a...
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
In this note, we consider the metric Ramsey problem for the normed spaces # p. Namely, given some 1
Yair Bartal, Nathan Linial, Assaf Naor
The main question studied in this article may be viewed as a non-linear analog of Dvoretzky's Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a nite metric...
Distributed paging [BFR92, ABF93b, AK95] deals with the dynamic allocation of copies of files in a distributed network as to minimize the total communication cost over a sequence of read and write...
Distributed paging [BFR92, ABF93b, AK95] deals with the dynamic allocation of copies of files in a distributed network as to minimize the total communication cost over a sequence of read and write...
Yair Bartal, John W. Byers, Danny Raz
We study combinatorial optimization problems in which a set of distributed agents must achieve a global objective using only local information. Papadimitriou and Yannakakis [15] initiated the study...
This paper gives a randomized competitive distributed paging algorithm called Heat & Dump. The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to...
Yair Bartal, Nathan Linial, Assaf Naor
The main question studied in this article may be viewed as a non-linear analog of Dvoretzky's Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a nite metric...
Rica Gonen School, Rica Gonen, Yair Bartal, Noam Nisan, Mira Gonen
ion rule describes a payment p j for each bidder j. We assume the bidders have quasi-linear utilities, so bidder j's overall utility for winning the set S j and paying p j is u j = v j (S j ) p...
Yossi Azar, Yair Bartal, Esteban Feuerstein, Stefano Leonardi
We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new...
We consider the k-server problem [23] in a distributed setting. Given a network of n processors, and k identical mobile servers, requests for service appear at the processors and a server must reach...
We deal with randomized competitive algorithms for non-preemptive call control on tree-like switching networks. We give an optimal O(log n) competitive algorithm for non-preemptive call scheduling on...
Annals of Mathematics, 162 (2005), 643–710 On metric Ramsey-type phenomena (2007)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky’s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric...
Embedding metric spaces in their intrinsic dimension (2007)
Ittai Abraham, Yair Bartal, Ofer Neiman
A fundamental question of metric embedding is whether the metric dimension of a metric space is related to its intrinsic dimension. That is whether the dimension in which it can be embedded in some...
Limitations to frechet embedding of metric spaces (2006)
Ittai Abraham, Yair Bartal, Ofer Neiman
In many application areas, complex data sets are often represented by some metric space and metric embedding is used to provide a more structured representation of the data. In many of these...
On the value of preemption in scheduling (2006)
Bartal, Yair, Leonardi, Stefano, Shallom, Gill, Sitters, Rene, Diaz, Josep, Jansen, Klaus, ...
Embedding Finite Metric Spaces in Low Dimension (2005)
This paper presents novel techniques that allow the solution to several open problems regarding embedding of finite metric spaces into Lp. We focus on proving near optimal bounds on the dimension...
Randomized k-server algorithms for growth-rate bounded graphs (2005)
Abstract The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total...
Metric Embeddings with Relaxed Guarantees (2005)
Ittai Abraham Yair, Yair Bartal, T-h. Hubert, Chan Kedar, Dhamdhere Anupam Gupta, Jon Kleinberg, ...
We consider the problem of embedding finite metrics with slack: we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be...
Metric Embeddings with Relaxed Guarantees (2005)
Ittai Abraham, Yair Bartal, T-h. Hubert, Chan Kedar, Dhamdhere Anupam Gupta, Jon Kleinberg, ...
We consider the problem of embedding finite metrics with slack: we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be...
Metric Embeddings with Relaxed Guarantees (2005)
Ittai Abraham, Yair Bartal, T-h. Hubert, Chan Kedar, Dhamdhere Anupam Gupta, Jon Kleinberg, ...
We consider the problem of embedding finite metrics with slack: we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be...
Metric embeddings with relaxed guarantees (2005)
Ittai Abraham, Yair Bartal, T-h. Hubert, Chan Kedar, Dhamdhere Anupam Gupta, Jon Kleinberg, ...
We consider the problem of embedding finite metrics with slack: we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be...
Online competitive algorithms for maximizing weighted throughput of unit jobs (2004)
Yair Bartal, Marek Chrobak, Wojciech Jawor, Ron Lavi
Abstract. We study an online buffer management problem for networks supporting Quality-of-Service (QoS) applications. Packets with different QoS values arrive at a network switch and are to be sent...
Dimension reduction for ultrametrics (2004)
Abstract We prove that an ultrametric on n points can be embedded in `dp with distortion at most 1 + ", and d = O("-2 log n). This bound matches the best known bound for the special...
Online competitive algorithms for maximizing weighted throughput of unit jobs (2004)
Yair Bartal, Marek Chrobak, Wojciech Jawor, Ron Lavi, ...
Abstract. We study an online bu#er management problem for networks supporting Quality-of-Service (QoS) applications. Packets with di#erent QoS values arrive at a network switch and are to be sent...
Online competitive algorithms for maximizing weighted throughput of unit jobs (2004)
Yair Bartal, Marek Chrobak, Wojciech Jawor, Ron Lavi
Abstract. We study an online scheduling problem for unit-length jobs, where each job is specified by its release time, deadline, and a nonnegative weight. The goal is to maximize the weighted...
Incentive compatible multi unit combinatorial auctions (2003)
Yair Bartal, Rica Gonen, Noam Nisan
This paper deals with multi-unit combinatorial auctions where there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where each bidder...
Limitations to Fréchet metric embedding method (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Abstract Fr'echet's classical isometric embedding argument has evolved to become a major toolin the study of metric spaces. An important example of a Fr'echet embedding is...
Incentive Compatible Multi Unit Combinatorial Auctions (2003)
Yair Bartal, Rica Gonen, Noam Nisan
The problem we deal with in this paper is a multi-unit combinatorial auction: there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where...
Incentive compatible multi unit combinatorial auctions (2003)
Yair Bartal, Rica Gonen, Noam Nisan
The problem we deal with in this paper is a multi-unit combinatorial auction: there are n types of goods for sale, and for each good there is some xed number of units. We focus on the case where each...
On metric Ramsey-type phenomena (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a non-linear analogue of Dvoretzky’s Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a finite metric...
Incentive compatible multi unit combinatorial auctions (2003)
Yair Bartal, Rica Gonen, Noam Nisan
The problem we deal with in this paper is a multi-unit combinatorial auction: there are n types of goods for sale, and for each i there are k i units of good i. We are interested in the case where...
Multi-embeddings and path-approximation of metric spaces (2003)
Metric embeddings have become a frequent tool in the design of algorithms. The applicability is often dependent on how high the embedding's distortion is. For example embedding into ultrametrics...
More on Random Walks, Electrical Networks, and the Harmonic k-Server Algorithm (2003)
Yair Bartal, Marek Chrobak, John Noga, Prabhakar Raghavan
Techniques from electrical network theory have been used to establish various properties of random walks. We explore this connection further, by showing how the classical formulas for the determinant...
A Generic Scheme for Building Overlay Networks in Adversarial Scenarios (2003)
Ittai Abraham, Baruch Awerbuch, Yossi Azar, Yair Bartal, Dahlia Malkhi, Elan Pavlov
This paper presents a generic scheme for a central, yet untackled issue in overlay dynamic networks: maintaining stability over long life and against malicious adversaries. The generic scheme...
Randomized k-Server Algorithms for Growth-Rate Bounded Graphs Yair Bartal (2003)
The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost....
On metric Ramsey-type phenomena (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky’s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric...
A Generic Scheme for Building Overlay Networks in Adversarial Scenarios (2003)
Ittai Abraham, Yossi Azar, Baruch Awerbuch, Yair Bartal, Dahlia Malkhi, Elan Pavlov
This paper presents a generic scheme for a central, yet untackled issue in overlay dynamic networks: maintaining stability over long life and against malicious adversaries. The generic scheme...
Limitations to Fréchet's Metric Embedding Method (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding [4]....
On Metric Ramsey-type Dichotomies (2002)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric...
On Metric Ramsey-type Dichotomies (2002)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric...
This paper gives a nearly logarithmic lower bound on the randomized competitive ratio for the Metrical Task Systems model [BLS92]. This implies a similar lower bound for the extensively studied...
On the competitive ratio of the work function algorithm for the k-server problem (2000)
Yair Bartal, Elias Koutsoupias
The k-server problem is one of the most fundamental online problems. The problem is to schedule k mobile servers to visit a sequence of points in a metric space with minimum total mileage. The...
On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem (2000)
Yair Bartal, Elias Koutsoupias
. The k-server problem is one of the most fundamental online problems. The problem is to schedule k mobile servers to serve a sequence of service points in a metric space to mimize the total mileage....
Firmato: A Novel Firewall Management Toolkit (1999)
Yair Bartal, Alain Mayer, Kobbi Nissim, Avishai Wool
In recent years firewalls have seen some impressive technological advances (e.g., stateful inspection, transparency, performance, etc) and wide-spread deployment. In contrast, firewall and security...
Firmato: A novel firewall management toolkit (1999)
Yair Bartal, Alain Mayer, Kobbi Nissim, Avishai Wool
In recent years packet-filtering firewalls have seen some impressive technological advances (e.g., stateful inspection, transparency, performance, etc.) and wide-spread deployment. In contrast,...
On Approximating Arbitrary Metrics by Tree Metrics (1998)
This paper is concerned with probabilistic approximation of metric spaces. In previous work we introduced the method of ecient approximation of metrics by more simple families of metrics in a...
Feedback-Free Multicast Prefix Protocols (1998)
Yair Bartal, John W. Byers, Michael Luby, Danny Raz
Developing scalable, reliable multicast protocols for lossy networks presents an array of challenges. In this work we focus on scheduling policies which determine what data the sender places into...
A Randomized Algorithm for Two Servers on the Line (1998)
Yair Bartal, Marek Chrobak, Lawrence L. Larmore
In the k-server problem we wish to minimize, in an online fashion, the movement cost of k servers in response to a sequence of requests. For 2 servers, it is known that the optimal deterministic...
Global Optimization Using Local Information with Applications to Flow Control (1997)
Yair Bartal, John W. Byers, Danny Raz
Flow control in high speed networks requires distributed routers to make fast decisions based only on local information in allocating bandwidth to connections. While most previous work on this...
Global Optimization Using Local Information with Applications to Flow Control (1997)
Yair Bartal, John W. Byers, Danny Raz
Flow control in high speed networks requires distributed routers to make fast decisions based only on local information in allocating bandwidth to connections. While most previous work on this...
On-line routing in all-optical networks (1997)
The paper deals with on-line routing in WDM (wavelength division multiplexing) optical networks. A sequence of requests arrives over time, each is a pair of nodes to be connected by a path. The...
A polylog(n)-competitive algorithm for metrical task systems (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log 6 n) against an oblivious adversary, on any metric space. This is the first...
On-line routing in all-optical networks (1997)
The paper deals with on-line routing in WDM (wavelength division multiplexing) optical networks. A sequence of requests arrives over time, each is a pair of nodes to be connected by a path. The...
Polylog(n)-Competitive Algorithm for Metrical Task Systems (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log 6 n) against an oblivious adversary, on any metric space. This is the first...
Polylog(n)-Competitive Algorithm For Metrical Task Systems (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log 6 n) for arbitrary metric spaces, against an oblivious adversary. This is the...
On-line Computation & Network Algorithms - Lecture 6 (1997)
who show that the Work Function Algorithm is 2k \Gamma 1-competitive. 6.1.1 The 2-Server Problem There are several known algorithms that achieve an optimal competitive ratio of 2 for the 2-server...
On Page Migration and Other Relaxed Task Systems (1997)
Yair Bartal, Moses Charikar, Piotr Indyk
This paper is concerned with the page migration (or le migration) problem [BS89] as part of a large class of on-line problems. The page migration problem deals with the management of pages residing...
A Modular Analysis of Network Transmission Protocols (1997)
Micah Adler, Yair Bartal, John W. Byers, Michael Luby, Danny Raz
We propose a new model for the analysis of data transmission protocols in lossy communication networks. The overall goal of a data transmission protocol is to successfully transmit a message from the...
Global Optimization Using Local Information with Applications to Flow Control (1997)
Yair Bartal, John W. Byers, Danny Raz
Flow control in high speed networks requires distributed routers to make fast decisions based only on local information in allocating bandwidth to connections. While most previous work on this...
A Modular Analysis of Network Transmission Protocols (1997)
Micah Adler, Yair Bartal, John W. Byers, Michael Luby, Danny Raz
We propose a new model for the analysis of data transmission protocols in lossy communication networks. The overall goal of a data transmission protocol is to successfully transmit a message from the...
Yair Bartal, John W. Byers, Danny Raz
Abstract. We study combinatorial optimization problems in which a set of distributed agents must achieve a global objective using only local information. Papadimitriou and Yannakakis [Proceedings of...
Abstract. We survey distributed data management problems including distributed paging, file allocation, and file migration. 1
Probabilistic approximation of metric spaces and its algorithmic applications (1996)
The goal of approximating metric spaces by more simple metric spaces has led to the notion of graph spanners [PU89, PS89] and to low-distortion embeddings in low-dimensional spaces [LLR94], having...
Multiprocessor Scheduling with Rejection (1996)
Yair Bartal, Stefano Leonardi, Alberto Marchetti-spaccamela, Jirí Sgall, Leen Stougie
We consider a version of multiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. An instance of the problem is given by m identical parallel machines and a...
Yossi Azar Yair, Yair Bartal, Esteban Feuerstein, Stefano Leonardi
. We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new...
Distributed Paging for General Networks (1996)
Baruch Awerbuch, Yair Bartal, Amos Fiat
Distributed paging [BFR92, ABF93b, AK95] deals with the dynamic allocation of copies of files in a distributed network as to minimize the total communication cost over a sequence of read and write...
Probabilistic Approximations of Metric Spaces and its Algorithmic Applications (1996)
The goal of approximating metric spaces by more simple metric spaces has led to the notion of graph spanners [PU89, PS89, ADDJS90, CDNS92] and to low-distortion embeddings in low-dimensional spaces...
Multiprocessor Scheduling with Rejection (1996)
Yair Bartal, Stefano Leonardi, Alberto Marchetti-spaccamela, Jirí Sgall, Leen Stougie
We consider a version of multiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. An instance of the problem is given by m identical parallel machines and a...
On-line Generalized Steiner Problem (1996)
Baruch Awerbuch, Yossi Azar, Yair Bartal
The Generalized Steiner Problem (GSP) is defined as follows. We are given a graph with non-negative weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph such...
Yair Bartal, Amos Fiat, Stefano Leonardi
We present lower bounds on the competitive ratio of randomized algorithms for a wide class of on-line graph optimization problems and we apply such results to on-line virtual circuit and optical...
A better lower bound for on-line scheduling (1994)
Yair Bartal, Howard Karloff, Yuval Rabani
We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the makespan, the...
Competitive Concurrent Distributed Data Structures (1994)
Baruch Awerbuch, Yair Bartal, Amos Fiat, Rainer Gawlick
this paper are ffl definition of semantics and complexity measures for distributed data structure for concurrent asynchrnous distributed directory access.
Distributively-Competitive Online Paging for Arbitrary-Topology Networks (Extended Abstract) (1994)
Baruch Awerbuch, Yair Bartal, Amos Fiat
) Baruch Awerbuch Yair Bartal y Amos Fiat y May 3, 1994 Abstract This paper gives first competitive distributed paging algorithm for the general network topology. The competitive ratios in storage...
Competitive Distributed File Allocation (1993)
Baruch Awerbuch, Yair Bartal, Amos Fiat
This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file...
Heat & Dump: Competitive Distributed Paging (1993)
Baruch Awerbuch, Yair Bartal, Amos Fiat
This paper gives a randomized competitive distributed paging algorithm called Heat & Dump. The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to...
Competitive Distributed File Allocation (1993)
Baruch Awerbuch, Yair Bartal, Amos Fiat
This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file...
Competitive Algorithms for Distributed Data Management (1992)
Yair Bartal, Amos Fiat, Yuval Rabani
We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([DF], [ML]), where copies of a file may be be stored in...
Competitive Algorithms for Distributed Data Management (1992)
Yair Bartal, Amos Fiat, Yuval Rabani
We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([DF], [ML]), where copies of a file may be be stored in...
The Harmonic k-Server Algorithm is Competitive (1991)
The k-server problem is a generalization of the paging problem, and is the most studied problem in the area of competitive online problems. The Harmonic algorithm is a very natural and simple...
Competitive Algorithms for Distributed Data Management
Yair Bartal, Amos Fiat, Yuval Rabani
We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([DF], [ML]), where copies of a file may be be stored in...