Arrow Research search

Author name cluster

Yair Bartal

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

49 papers
2 author rows

Possible papers

49

AAAI Conference 2025 Conference Paper

Improved Fixed-Parameter Bounds for Min-Sum-Radii and Diameters k-Clustering and Their Fair Variants

  • Sandip Banerjee
  • Yair Bartal
  • Lee-Ad Gottlieb
  • Alon Hovav

We provide improved upper and lower bounds for the Min-Sum-Radii (MSR) and Min-Sum-Diameters (MSD) clustering problems with a bounded number of clusters k. In particular, we propose an exact MSD algorithm with running-time n^O(k). We also provide (1 + Ɛ) approximation algorithms for both MSR and MSD with running-times of O(kn) + (1/Ɛ)^O(dk) in metrics spaces of doubling dimension d. Our algorithms extend to k-center, improving upon previous results, and to α-MSR, where radii are raised to the α power for α > 1. For α-MSD we prove an exponential time ETH-based lower bound for α > log 3. All algorithms can also be modified to handle outliers. Moreover, we can extend the results to variants that observe fairness constraints, as well as to the general framework of mergeable clustering, which includes many other popular clustering variants. We complement these upper bounds with ETH-based lower bounds for these problems, in particular proving that n^O(k) time is tight for MSR and α-MSR even in doubling spaces, and that 2^o(k) bounds are impossible for MSD.

PDF Details DOI

FOCS Conference 2024 Conference Paper

Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications

  • Sandip Banerjee
  • Yair Bartal
  • Lee-Ad Gottlieb
  • Alon Hovav

We present a refined construction of hierarchical probabilistic partitions with novel properties, substantially stronger than previously known. Our construction provides a family of hierarchical partitions enabling fast dynamic programming algorithms, by guaranteeing that given a sparse set of balls, each cell of the hierarchical partition intersects only a small number of balls. The number of balls intersecting a cell is bounded solely as a function of the padding parameter of the partition (which is bounded in particular by the doubling dimension). This is in contrast to standard guarantees for probabilistic partitions which holds only in expectation. Additionally, each cell of our partition has a significantly smaller description than in previous constructions. These novel partition properties allow faster dynamic programs for a wide spectrum of fundamental problems defined by inherent or implicit sparsity. Among our main applications highlighting the utility of the novel properties are two well-studied clustering problems: min-sum radii (MSR) and min-sum diameters (MSD) clustering. The input to both these problems is a metric space and an integer $k$, and the goal is to partition the space into $k$ clusters so as to minimize the sum of radii or diameters of the clusters, respectively. We apply our construction to give dramatically improved exact and approximation algorithms for these problems in Euclidean and doubling spaces, planar graphs, and more general settings. In particular, we obtain for these problems the first PTAS for doubling spaces, improving and generalizing upon the time bounds known for Euclidean space, even achieving linear time algorithms for fixed parameter $k$. We also obtain the first PTAS for MSR for all metrics of bounded padding parameter, including planar and minor excluded metrics. Moreover, our results extend to constrained variants such as fair MSR and mergeable MSR, dramatically improving upon the best known results on these problems in low dimension. Our methods also extend to other clustering problems, including $\alpha$ -MSR and $\alpha$ -MSD (where the measure is the sum of radii or diameters raised to power of $\alpha$ ), as well as aversion clustering, providing in similar settings the first QPTAS and first fixed parameter PTAS for these problems. Moreover, many of our clustering results extend to the corresponding clustering problems with outliers. Our construction applies as well to a wide range of network design problems possessing inherent sparsity properties in doubling spaces. Notably, we can apply our method to dramatically improve upon the best known bounds for the traveling salesman (TSP) and Steiner tree problems in doubling spaces. Similarly, we significantly improve upon the best known runtimes for Steiner forest, TSP with neighborhoods, prize collecting TSP, and 2-ECSS (two edge-connected spanning subgraph), all in doubling spaces. Our new constructions of hierarchical probabilistic partitions present a major simplification of previous methods, and provide a more natural and useful tool for future applications.

Details

STOC Conference 2021 Conference Paper

Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces

  • Yair Bartal
  • Lee-Ad Gottlieb

We give an algorithm that computes a (1+є)-approximate Steiner forest in near-linear time n · 2 (1/є) O ( ddim 2 ) (loglog n ) 2 , where ddim is the doubling dimension of the metric space. This improves upon the best previous result due to Chan et al. (SIAM J. Comput. 4 (2018)), who gave a runtime of about n 2 O ( ddim ) · 2 ( ddim /є) O ( ddim ) √log n . For Steiner tree our methods achieve an even better runtime n (log n ) (1/є) O ( ddim 2 ) .

Details

SODA Conference 2020 Conference Paper

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds

  • Yair Bartal
  • Nova Fandina
  • Seeun William Umboh

Probabilistic metric embedding into trees is a powerful technique for designing online algorithms. The standard approach is to embed the entire underlying metric into a tree metric and then solve the problem on the latter. The overhead in the competitive ratio depends on the expected distortion of the embedding, which is logarithmic in n, the size of the underlying metric. For many online applications, such as online network design problems, it is natural to ask if it is possible to construct such embeddings in an online fashion such that the distortion would be a polylogarithmic function of k, the number of terminals. Our first main contribution is answering this question negatively, exhibiting a lower bound of (log k log ɸ), where ɸ is the aspect ratio of the set of terminals, showing that a simple modification of the probabilistic embedding into trees of Bartal (FOCS 1996), which has expected distortion of O (log k log ɸ), is nearly-tight. Unfortunately, this may result in a very bad (polynomial) dependence in terms of k. Our second main contribution is a general framework for bypassing this limitation. We show that for a large class of online problems this online probabilistic embedding can still be used to devise an algorithm with O (min{log k log( k λ), log 3 k }) overhead in the competitive ratio, where k is the current number of terminals, and λ is a measure of subadditivity of the cost function, which is at most r, the current number of requests. In particular, this implies the first algorithms with competitive ratio polylog( k ) for online subadditive network design ( buy-at-bulk network design being a special case), and polylog( k, r ) for online group Steiner forest.

Details

TCS Journal 2019 Journal Article

Approximate nearest neighbor search for ℓ-spaces (2 < p < ∞) via embeddings

  • Yair Bartal
  • Lee-Ad Gottlieb

While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and ℓ 1, few non-trivial algorithms are known for ℓ p when 2 < p < ∞. In this paper, we revisit this fundamental problem and present approximate nearest-neighbor search algorithms which give the best known approximation factor guarantees in this setting.

Details DOI

NeurIPS Conference 2019 Conference Paper

Dimensionality reduction: theoretical perspective on practical measures

  • Yair Bartal
  • Nova Fandina
  • Ofer Neiman

Dimensionality reduction plays a central role in real-world applications for Machine Learning, among many fields. In particular, metric dimensionality reduction where data from a general metric is mapped into low dimensional space, is often used as a first step before applying machine learning algorithms. In almost all these applications the quality of the embedding is measured by various average case criteria. Metric dimensionality reduction has also been studied in Math and TCS, within the extremely fruitful and influential field of metric embedding. Yet, the vast majority of theoretical research has been devoted to analyzing the worst case behavior of embeddings and therefore has little relevance to practical settings. The goal of this paper is to bridge the gap between theory and practice view-points of metric dimensionality reduction, laying the foundation for a theoretical study of more practically oriented analysis. This paper can be viewed as providing a comprehensive theoretical framework addressing a line of research initiated by VL [NeuroIPS' 18] who have set the goal of analyzing different distortion measurement criteria, with the lens of Machine Learning applicability, from both theoretical and practical perspectives. We complement their work by considering some important and vastly used average case criteria, some of which originated within the well-known Multi-Dimensional Scaling framework. While often studied in practice, no theoretical studies have thus far attempted at providing rigorous analysis of these criteria. In this paper we provide the first analysis of these, as well as the new distortion measure developed by [VL18] designed to possess Machine Learning desired properties. Moreover, we show that all measures considered can be adapted to possess similar qualities. The main consequences of our work are nearly tight bounds on the absolute values of all distortion criteria, as well as first approximation algorithms with provable guarantees.

PDF Details

SODA Conference 2016 Conference Paper

On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion

  • Yair Bartal
  • Arnold Filtser
  • Ofer Neiman

Minimum Spanning Trees of weighted graphs are fundamental objects in numerous applications. In particular in distributed networks, the minimum spanning tree of the network is often used to route messages between network nodes. Unfortunately, while being most efficient in the total cost of connecting all nodes, minimum spanning trees fail miserably in the desired property of approximately preserving distances between pairs. While known lower bounds exclude the possibility of the worst case distortion of a tree being small, it was shown in [4] that there exists a spanning tree with constant average distortion. Yet, the weight of such a tree may be significantly larger than that of the MST. In this paper, we show that any weighted undirected graph admits a spanning tree whose weight is at most (1 + ρ ) times that of the MST, providing constant average distortion O (1/ ρ 2 ). 1 The constant average distortion bound is implied by a stronger property of scaling distortion, i. e. , improved distortion for smaller fractions of the pairs. The result is achieved by first showing the existence of a low weight spanner with small prioritized distortion, a property allowing to prioritize the nodes whose associated distortions will be improved. We show that prioritized distortion is essentially equivalent to coarse scaling distortion via a general transformation, which has further implications and may be of independent interest. In particular, we obtain an embedding for arbitrary metrics into Euclidean space with optimal prioritized distortion.

Details

FOCS Conference 2013 Conference Paper

A Linear Time Approximation Scheme for Euclidean TSP

  • Yair Bartal
  • Lee-Ad Gottlieb

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. The special case of TSP in bounded-dimensional Euclidean spaces has been a particular focus of research: The celebrated results of Arora [Aro98] and Mitchell [Mit99] - along with subsequent improvements of Rao and Smith [RS98] - demonstrated a polynomial time approximation scheme for this problem, ultimately achieving a runtime of O d, ε (n log n). In this paper, we present a linear time approximation scheme for Euclidean TSP, with runtime O d, ε (n). This improvement resolves a 15 year old conjecture of Rao and Smith, and matches for Euclidean spaces the bound known for a broad class of planar graphs [Kle08].

Details

TCS Journal 2013 Journal Article

Bandwidth and low dimensional embedding

  • Yair Bartal
  • Douglas E. Carroll
  • Adam Meyerson
  • Ofer Neiman

We design an algorithm to embed graph metrics into ℓ p with dimension and distortion both dependent only upon the bandwidth of the graph. In particular, we show that any graph of bandwidth k embeds with distortion polynomial in k into ℓ p O ( log k ), 1 ⩽ p ⩽ ∞. Prior to our result the only known embedding with distortion independent of n was into high dimensional ℓ 1 and had distortion exponential in k. Our low dimensional embedding is based on a general method for reducing the dimension of an ℓ p embedding. This method requires that the embedding satisfy certain conditions, and the dimension is reduced to the intrinsic dimension of the point set, without substantially increasing the distortion. We observe that the family of graphs with bounded bandwidth are doubling, thus our main result can be viewed as a positive answer to a conjecture of Assouad (1983) [2], limited to this family. We also study an extension to graphs of bounded tree-bandwidth.

Details DOI

STOC Conference 2012 Conference Paper

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

  • Yair Bartal
  • Lee-Ad Gottlieb
  • Robert Krauthgamer

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+µ)-approximation to the optimal tour, for any fixed µ>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora [Aro98] and Mitchell [Mit99] prove that the above result holds in the special case of TSP in a fixed-dimensional Euclidean space. Thus, our algorithm demonstrates that the algorithmic tractability of metric TSP depends on the dimensionality of the space and not on its specific geometry. This result resolves a problem that has been open since the quasi-polynomial time algorithm of Talwar [Tal04].

Details

SODA Conference 2011 Conference Paper

Fast, precise and dynamic distance queries

  • Yair Bartal
  • Lee-Ad Gottlieb
  • Tsvi Kopelowitz
  • Moshe Lewenstein
  • Liam Roditty

We present an approximate distance oracle for a point set S with n points and doubling dimension Λ. For every ε > 0, the oracle supports (1 + ε)-approximate distance queries in (universal) constant time, occupies space [ε − O (Λ) + 2 O (Λ log Λ) ] n, and can be constructed in [2 O (Λ) log 3 n + ε − O (Λ) + 2 O (Λ log Λ) ] n expected time. This improves upon the best previously known constructions, presented by Har-Peled and Mendel [13]. Furthermore, the oracle can be made fully dynamic with expected O (1) query time and only 2 O (Λ) log n + ε − O (Λ) + 2 O (Λ log Λ) update time. This is the first fully dynamic (1 + ε)-distance oracle.

Details

SODA Conference 2009 Conference Paper

On low dimensional local embeddings

  • Ittai Abraham
  • Yair Bartal
  • Ofer Neiman

We study the problem of embedding metric spaces into low dimensional ℓ p spaces while faithfully preserving distances from each point to its k nearest neighbors. We show that any metric space can be embedded into with k -local distortion of O ((log k )/ p ). We also show that any ultrametric can be embedded into with k -local distortion 1 + ∊. Our embedding results have immediate applications to local Distance Oracles. We show how to preprocess a graph in polynomial time to obtain a data structure of O ( nk 1/t log 2 k ) bits, such that distance queries from any node to its k nearest neighbors can be answered with stretch O ( t ).

Details

FOCS Conference 2008 Conference Paper

Nearly Tight Low Stretch Spanning Trees

  • Ittai Abraham
  • Yair Bartal
  • Ofer Neiman

We prove that any graph G with n points has a distribution T over spanning trees such that for any edge (u, v) the expected stretch E T~T [d T (u, nu)/d G (u, nu)] is bounded by Otilde(log n). Our result is obtained via a new approach of building "highways" between portals and a new strong diameter probabilistic decomposition theorem.

Details

STOC Conference 2007 Conference Paper

Local embeddings of metric spaces

  • Ittai Abraham
  • Yair Bartal
  • Ofer Neiman

In many application areas, complex data sets are often representedby some metric space and metric embedding is used to provide a more structured representation of the data. In many of these applications much greater emphasis is put on the preserving the local structure of the original space than on maintaining its complete structure. This is also the case in some networking applications where "small world" phenomena in communication patterns has been observed. Practical study of embedding has indeed involved with finding embeddings with this property. In this paper we initiate thestudy of local embeddings of metric spaces and provide embeddings with distortion depending solely on the local structureof the space.

Details

STOC Conference 2006 Conference Paper

Advances in metric embedding theory

  • Ittai Abraham
  • Yair Bartal
  • Ofer Neiman

Metric Embedding plays an important role in a vast range of application areas such as computer vision, computational biology, machine learning, networking, statistics, and mathematical psychology, to name a few.The theory of metric embedding received much attention in recent years by mathematicians as well as computer scientists and has been applied in many algorithmic applications.A cornerstone of the field is a celebrated theorem of Bourgain which states that every finite metric space on n points embeds in Euclidean space with O(log n) distortion.Bourgain's result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, it is possible that an embedding can do much better in terms of the average distortion .Indeed, in most practical applications of metric embedding the main criteria for the quality of an embedding is its average distortion over all pairs.In this paper we provide an embedding with constant average distortion for arbitrary metric spaces, while maintaining the same worst case bound provided by Bourgain's theorem.In fact, our embedding possesses a much stronger property. We define the l q -distortion of a uniformly distributed pair of points. Our embedding achieves the best possible l q -distortion for all 1 ≤ q ≤ ∞ simultaneously .These results have several algorithmic implications, e.g. an O(1) approximation for the unweighted uncapacitated quadratic assignment problem.The results are based on novel embedding methods which improve on previous methods in another important aspect: the dimension .The dimension of an embedding is of very high importance in particular in applications and much effort has been invested in analyzing it. However, no previous result improved the bound on the dimension which can be derived from Bourgain's embedding.We prove that any metric space on n points embeds into L p with distortion O(log n) in dimension O(log n). This provides an optimal bound on the dimension of the embedding.Somewhat surprisingly, we show that a further small improvement is possible at a small price in the distortion, obtaining an embedding with distortion O(log 1+θ n) in optimal dimension O(θ -1 log n/log log n), for any θ > 0. It is worth noting that with the small loss in the distortion this improves upon the best known embedding of arbitrary spaces into Euclidean space, where dimension reduction is used.Our techniques also allow to obtain the optimal distortion for embedding into L p with nearly tight dimension. For any 1 ≤ p ≤ ⊂ and any 1 ≤ k ≤ p, we give an embedding into L p with distortion O(⌈ log n/k ⌉) in dimension 2 O(k) log n.Underlying our results is a novel embedding method. Probabilistic metric decomposition techniques have played a central role in the field of finite metric embedding in recent years. Here we introduce a novel notion of probabilistic metric decompositions which comes particularly natural in the context of embedding. Our new methodology provides a unified approach to all known results on embedding of arbitrary metric spaces. Moreover, as described above, with some additional ideas they allow to get far stronger results. These metric decompositions seem of independent interest.

Details

FOCS Conference 2005 Conference Paper

Metric Embeddings with Relaxed Guarantees

  • Ittai Abraham
  • Yair Bartal
  • T. -H. Hubert Chan
  • Kedar Dhamdhere
  • Anupam Gupta 0001
  • Jon M. Kleinberg
  • Ofer Neiman
  • Aleksandrs Slivkins

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 arbitrarily distorted. This definition is motivated by recent research in the networking community, which achieved striking empirical success at embedding Internet latencies with low distortion into low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler (2004), we show that provable guarantees of this type can in fact be achieved in general: any finite metric can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into /spl lscr//sub 1/ which exhibit gracefully degrading distortion: these is a single embedding into /spl lscr//sub 1/ that achieves distortion at most O(log 1//spl epsi/) on all but at most an /spl epsi/ fraction of distances, simultaneously for all /spl epsi/ > 0. We extend this with distortion O(log 1//spl epsi/)/sup 1/p/ to maps into general /spl lscr//sub p/, p /spl ges/ 1 for several classes of metrics, including those with bounded doubling dimension and those arising from the shortest-path metric of a graph with an excluded minor. Finally, we show that many of our constructions are tight, and give a general technique to obtain lower bounds for /spl epsi/-slack embeddings from lower bounds for low-distortion embeddings.

Details

TCS Journal 2004 Journal Article

On the competitive ratio of the work function algorithm for the k-server problem

  • 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 k-server conjecture of Manasse, McGeogh, and Sleator states that there exists a k-competitive online algorithm. The conjecture has been open for over 15 years. The top candidate online algorithm for settling this conjecture is the work function algorithm (WFA) which was shown to have competitive ratio at most 2k−1. In this paper, we lend support to the conjecture that WFA is in fact k-competitive by proving that it achieves this ratio in several special metric spaces: the line, the star, and all metric spaces with k+2 points.

Details DOI

TCS Journal 2004 Journal Article

On-line generalized Steiner problem

  • Baruch Awerbuch
  • Yossi Azar
  • Yair Bartal

The generalized Steiner problem (GSP) is defined as follows. We are given a graph with non-negative edge weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph such that the two nodes of each pair are connected by a path. Off-line GSP approximation algorithms were given in Agarwal et al. (SIAM J. Comput. 24(3) (1995) 440) and Goemans and Williamson (SIAM J. Comput. 24(2) (1995) 296). We consider the on-line GSP, in which pairs of vertices arrive on-line and are needed to be connected immediately. We show that the online Min-Cost (i. e. greedy) strategy for this problem has O(log 2 n) competitive ratio. The previous best algorithm was O( n log n) competitive (Workshop on Algorithms and Data Structures, 1993, pp. 622–633). Following this work a different (non-greedy) algorithm has been shown to achieve an O(log n) competitive ratio (Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 344–353). We also consider the network connectivity leasing problem which is a generalization of the GSP. Here, edges of the graph can be either bought or leased for different costs. We provide simple randomized algorithm based on on-line generalized Steiner algorithms whose competitive ratio is within a constant factor of the best competitive algorithm for the on-line GSP.

Details DOI

I&C Journal 2003 Journal Article

Competitive distributed file allocation

  • Baruch Awerbuch
  • Yair Bartal
  • Amos Fiat

This paper deals with the file allocation problem [6] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file re-allocation strategy that adapts on-line to a sequence of read and write requests whose location and relative frequencies are completely unpredictable. This is achieved by replicating the file in response to read requests and migrating the file in response to write requests while paying the associated communications costs, so as to be closer to processors that access it frequently. We develop first explicit deterministic on-line strategy assuming existence of global information about the state of the network; previous (deterministic) solutions were complicated and more expensive. Our solution has (optimal) logarithmic competitive ratio. The paper also contains the first explicit deterministic data migration [7] algorithm achieving the best known competitive ratio for this problem. Using somewhat different technique, we also develop the first deterministic distributed file allocation algorithm (using only local information) with poly-logarithmic competitive ratio against a globally optimized optimal prescient strategy.

Details DOI

TARK Conference 2003 Conference Paper

Incentive compatible multi unit combinatorial auctions

  • 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 desires a relatively small number of units of each good. In particular, this includes the case where each good has exactly k units, and each bidder desires no more than a single unit of each good. We provide incentive compatible mechanisms for combinatorial auctions for the general case where bidders are not limited to singleminded valuations. The mechanisms we give have approximation ratios close to the best possible for both on-line and off-line scenarios. This is the first result where non-VCG mechanisms are derived for non-single minded bidders for a natural model of combinatorial auctions.

Details

STOC Conference 2003 Conference Paper

On metric ramsey-type phenomena

  • Yair Bartal
  • Nati Linial
  • Manor Mendel
  • Assaf Naor

This paper deals with Ramsey-type theorems for metric spaces. Such a theorem states that every n point metric space contains a large subspace which can be embedded with some fixed distortion in a metric space from some special class.Our main theorem states that for any ε>0 , every n point metric space contains a subspace of size at least n 1-ε which is embeddable in an ultrametric with O(log(1/ε)/ε distortion. This in particular provides a bound for embedding in Euclidean spaces. The bound on the distortion is tight up to the log(1/ε) factor even for embedding in arbitrary Euclidean spaces. This result can be viewed as a non-linear analog of Dvoretzky's theorem, a cornerstone of modern Banach space theory and convex geometry.Our main Ramsey-type theorem and techniques naturally extend to give theorems for classes of hierarchically well-separated trees which have algorithmic implications, and can be viewed as the solution of a natural clustering problem.We further include a comprehensive study of various other aspects of the metric Ramsey problem.

Details

FOCS Conference 2001 Conference Paper

A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems

  • Yair Bartal
  • Béla Bollobás
  • Manor Mendel

The paper gives a nearly logarithmic lower bound on the randomized competitive ratio for a Metrical Task Systems model (A. Borodin et al. , 1992). This implies a similar lower bound for the extensively studied K-server problem. Our proof is based on proving a Ramsey-type theorem for metric spaces. In particular, we prove that in every metric space there exists a large subspace which is approximately a "hierarchically well-separated tree" (HST) (Y. Bartal, 1996). This theorem may be of independent interest.

Details

STOC Conference 2001 Conference Paper

Approximating min-sum k -clustering in metric spaces

  • Yair Bartal
  • Moses Charikar
  • Danny Raz

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 cluster. We give the first polynomial time non-trivial approximation algorithm for this problem. The algorithm provides an $\ratio$ approximation to the min-sum k -clustering problem in general metric spaces, with running time $\runtime$. The result is based on embedding of metric spaces into hierarchically separated trees. We also provide a bicriteria approximation result that provides a constant approximation factor solution with only a constant factor increase in the number of clusters. This result is obtained by modifying and drawing ideas from recently developed primal dual approximation algorithms for facility location.

Details

TCS Journal 2001 Journal Article

On page migration and other relaxed task systems

  • Yair Bartal
  • Moses Charikar
  • Piotr Indyk

This paper is concerned with the page migration (or file migration) problem (Black and Sleator, Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989) as part of a large class of on-line problems. The page migration problem deals with the management of pages residing in a network of processors. In the classical problem there is only one copy of each page which is accessed by different processors over time. The page is allowed to be migrated between processors. However a migration incurs higher communication cost than an access (proportionally to the page size). The problem is that of deciding when and where to migrate the page in order to lower access costs. A more general setting is the k-page migration problem where we wish to maintain k copies of the page. The page migration problems are concerned with a dilemma common to many on-line problems: determining when it is beneficial to make configuration changes. We deal with the relaxed task systems model which captures a large class of problems of this type, that can be described as the generalization of some original task system problem (Borodin et al. , J. ACM 39(4) (1992) 745–763). Given a c-competitive algorithm for a task system we show how to obtain a deterministic O(c2) and randomized O(c) competitive algorithms for the corresponding relaxed task system. The result implies deterministic algorithms for k-page migration by using k-server (Manasse et al. , J. Algorithms 11(2) (1990) 208–230) algorithms, and for network leasing by using generalized Steiner tree algorithms (Awerbuch et al. , Proc 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 1996, pp. 68–74), as well as providing solutions for natural generalizations of other problems (e. g. storage rearrangement (Fiat et al. , Proc. 36th Ann. IEEE Symp. on Foundations of Computer Science, October 1995, pp. 392–403). We further study some special cases of the k-page migration problem and get optimal deterministic algorithms. For the classical page migration problem we present a deterministic algorithm that achieves a competitive ratio of ∼4. 086, improving upon the previously best competitive ratio of 7 (Awerbuch et al. , Proc. 25th ACM Symp. on Theory of Computing, May 1993, pp. 164–173). (The current lower bound on the problem is ∼3. 148 (Chrobak et al. , J. Algorithms 24(1) (1997) 124–157).)

Details DOI

I&C Journal 2000 Journal Article

A Randomized Algorithm for Two Servers on the Line

  • 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 two servers, it is known that the optimal deterministic algorithm has competitive ratio 2, and it has been a long-standing open problem whether it is possible to improve this ratio using randomization. We give a positive answer to this problem when the underlying metric space is a real line, by providing a randomized online algorithm for this case with competitive ratio at most 155 78 ≈1. 987. This is the first algorithm for two servers that achieves a competitive ratio smaller than 2 in a nonuniform metric space with more than three points. We consider a more general problem called the (k, l)-server problem, in which a request is served using l out of k available servers. We show that the randomized 2-server problem can be reduced to the deterministic (2l, l)-server problem. We prove a lower bound of 2 on the competitive ratio of the (4, 2)-server problem. This implies that one unbiased random bit is not sufficient to improve the ratio of 2 for the two-server problem. Then we give a 155 78 -competitive algorithm for the (6, 3)-server problem on the real line. Our algorithm is simple and memoryless. The solution has been obtained using linear programming techniques that may have applications for other online problems.

Details DOI

TCS Journal 1999 Journal Article

Ondashline routing in all-optical networks

  • Yair Bartal
  • Stefano Leonardi

The paper deals with ondashline routing in wavelength division multiplexing (WDM) optical networks. A sequence of requests arrives over time, each is a pair of nodes to be connected by a path. The problem is to assign a wavelength and a path to each pair, so that no two paths sharing a link are assigned the same wavelength. The goal is to minimize the number of wavelengths used to establish all connections. Raghavan and Upfal (Proc. 26th Annual Symp. on Theory of Computing, 1994, pp. 133–143) considered the off-line version of the problem, which was further studied in Aumann and Rabani (Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, 1995, pp. 567–576), Kaklamanis and Persiano (Proc. 4th Annual European Symp. on Algorithms, Lecture Notes in Computer Science, vol. 1136, Springer, Berlin, 1996, pp. 460–470), Mihail et al. (Proc. 36th IEEE Annual Symp. on Foundations of Computer Science, 1995, pp. 548–557), Rabani, (Proc. 37th Annual Symp. on Foundations of Computer Science, 1996, pp. 400–409). For a line topology, the problem is the well-studied interval graph coloring problem. Ondashline algorithms for this problem have been analyzed in Kierstead and Trotter (Congr. Numer. 33 (1981) 143–153). We consider trees, trees of rings, and meshes topologies, previously studied in the off-line case. We give ondashline algorithms with competitive ratio O(log n) for all these topologies. We give a matching Ω(log n) lower bound for meshes. We also prove that any algorithm for trees cannot have competitive ratio better than Ω(log n/log log n). We also consider the problem where every edge is associated with parallel links. While in WDM technology, a fiber link requires different wavelengths for every transmission, space division multiplexing technology allows parallel links for a single wavelength, at an additional cost. Thus, it may be beneficial in terms of network economics to combine between the two technologies (this is indeed done in practice). For arbitrary networks with Ω(log n) parallel links we give an ondashline algorithm with competitive ratio O(log n).

Details DOI

FOCS Conference 1997 Conference Paper

Global Optimization Using Local Information with Applications to Flow Control

  • 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 problem focuses on achieving local objective functions, in many cases it may be necessary to achieve global objectives such as maximizing the total flow. This problem illustrates one of the basic aspects of distributed computing: achieving global objectives using local information. Papadimitriou and Yannakakis (1993) initiated the study of such problems in a framework of solving positive linear programs by distributed agents. We take their model further, by allowing the distributed agents to acquire more information over time. We therefore turn attention to the tradeoff between the running time and the quality of the solution to the linear program. We give a distributed algorithm that obtains a (1+/spl epsiv/) approximation to the global optimum solution and runs in a polylogarithmic number of distributed rounds. While comparable in running time, our results exhibit a significant improvement on the logarithmic ratio previously obtained by Awerbuch and Azar (1994). Our algorithm, which draws from techniques developed by Luby and Nisan (1993) is considerably simpler than previous approximation algorithms for positive linear programs, and thus may have practical value in both centralized and distributed settings.

Details

FOCS Conference 1996 Conference Paper

Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications

  • Yair Bartal

This paper provides a novel technique for the analysis of randomized algorithms for optimization problems on metric spaces, by relating the randomized performance ratio for any, metric space to the randomized performance ratio for a set of "simple" metric spaces. We define a notion of a set of metric spaces that probabilistically-approximates another metric space. We prove that any metric space can be probabilistically-approximated by hierarchically well-separated trees (HST) with a polylogarithmic distortion. These metric spaces are "simple" as being: (1) tree metrics; (2) natural for applying a divide-and-conquer algorithmic approach. The technique presented is of particular interest in the context of on-line computation. A large number of on-line algorithmic problems, including metrical task systems, server problems, distributed paging, and dynamic storage rearrangement are defined in terms of some metric space. Typically for these problems, there are linear lower bounds on the competitive ratio of deterministic algorithms. Although randomization against an oblivious adversary has the potential of overcoming these high ratios, very little progress has been made in the analysis. We demonstrate the use of our technique by obtaining substantially improved results for two different on-line problems.

Details

FOCS Conference 1993 Conference Paper

Heat & Dump: Competitive Distributed Paging

  • Baruch Awerbuch
  • Yair Bartal
  • Amos Fiat

This paper gives a randomized competitive distributed paging algorithm called Heat and Dump, The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to within a constant factor. This is in contrast to the linear optimal deterministic competitive ratio. >

Details

FOCS Conference 1992 Conference Paper

The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms

  • Yair Bartal
  • Adi Rosén

The authors consider the k-server problem 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 the request point. Besides modeling problems in computer networks where k identical mobile resources are shared by the processors of the network, this models a realistic situation where the transfer of information is costly and there is no central control that governs the behavior of servers that move around to satisfy requests for service. The problem is that of devising algorithms that minimize not only the travel of the server but also the communication cost incurred for the transmission of control messages. The main contribution is a general translator to transform any deterministic global-control competitive k-server algorithm into a distributed competitive one. As consequences they get poly(k)-competitive distributed algorithms for the line, trees and the ring. >

Details
v2026.09.13