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.

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.

It is well known that the Johnson-Lindenstrauss dimensionality reduction method is optimal for worst case distortion. While in practice many other methods and heuristics are used, not much is known in terms of bounds on their performance. The question of whether the JL method is optimal for practical measures of distortion was recently raised in [Yair Bartal et al., 2019] (NeurIPS'19). They provided upper bounds on its quality for a wide range of practical measures and showed that indeed these are best possible in many cases. Yet, some of the most important cases, including the fundamental case of average distortion were left open. In particular, they show that the JL transform has 1+ε average distortion for embedding into k-dimensional Euclidean space, where k = O(1/ε²), and for more general q-norms of distortion, k = O(max{1/ε²,q/ε}), whereas tight lower bounds were established only for large values of q via reduction to the worst case. In this paper we prove that these bounds are best possible for any dimensionality reduction method, for any 1 ≤ q ≤ O((log (2ε² n))/ε) and ε ≥ 1/(√n), where n is the size of the subset of Euclidean space. Our results also imply that the JL method is optimal for various distortion measures commonly used in practice, such as stress, energy and relative error. We prove that if any of these measures is bounded by ε then k = Ω(1/ε²), for any ε ≥ 1/(√n), matching the upper bounds of [Yair Bartal et al., 2019] and extending their tightness results for the full range moment analysis. Our results may indicate that the JL dimensionality reduction method should be considered more often in practical applications, and the bounds we provide for its quality should be served as a measure for comparison when evaluating the performance of other methods and heuristics.

A tree cover of a metric space (X,d) is a collection of trees, so that every pair x,y∈X has a low distortion path in one of the trees. If it has the stronger property that every point x∈X has a single tree with low distortion paths to all other points, we call this a Ramsey tree cover. In this paper we devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small. In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers.

We give an algorithm that computes a (1+є)-approximate Steiner forest in near-linear time n · 2(1/є)O(ddim2) (loglogn)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 n2O(ddim) · 2(ddim/є)O(ddim) √logn. For Steiner tree our methods achieve an even better runtime n (logn)(1/є)O(ddim2).

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λ), log3 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.

A tree cover of a metric space (X,d) is a collection of trees, so that every pair x,y in X has a low distortion path in one of the trees. If it has the stronger property that every point x in X has a single tree with low distortion paths to all other points, we call this a Ramsey tree cover. Tree covers and Ramsey tree covers have been studied by [Yair Bartal et al., 2005; Anupam Gupta et al., 2004; T-H. Hubert Chan et al., 2005; Gupta et al., 2006; Mendel and Naor, 2007], and have found several important algorithmic applications, e.g. routing and distance oracles. The union of trees in a tree cover also serves as a special type of spanner, that can be decomposed into a few trees with low distortion paths contained in a single tree; Such spanners for Euclidean pointsets were presented by [S. Arya et al., 1995]. In this paper we devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small. In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers.

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.

For Euclidean space (l_2), there exists the powerful dimension reduction transform of Johnson and Lindenstrauss [Conf. in modern analysis and probability, AMS 1984], with a host of known applications. Here, we consider the problem of dimension reduction for all l_p spaces 1<p<2. Although strong lower bounds are known for dimension reduction in l_1, Ostrovsky and Rabani [JACM 2002] successfully circumvented these by presenting an l_1 embedding that maintains fidelity in only a bounded distance range, with applications to clustering and nearest neighbor search. However, their embedding techniques are specific to l_1 and do not naturally extend to other norms. In this paper, we apply a range of advanced techniques and produce bounded range dimension reduction embeddings for all of 1<p<2, thereby demonstrating that the approach initiated by Ostrovsky and Rabani for l_1 can be extended to a much more general framework. We also obtain improved bounds in terms of the intrinsic dimensionality. As a result we achieve improved bounds for proximity problems including snowflake embeddings and clustering.

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.

The traveling salesman problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem an algorithm that for any fixed $\varepsilon>0$ computes in randomized polynomial time a $(1+\varepsilon)$-approximation to the optimal tour in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora [J. ACM, 45 (1998), pp. 753--782] and Mitchell [SIAM J. Comput., 28 (1999), pp. 1298--1309] 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 [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 281--290].

This paper addresses the basic question of how well a tree can approximate distances of a metric space or a graph. Given a graph, the problem of constructing a spanning tree in a graph which strongly preserves distances in the graph is a fundamental problem in network design. We present scaling distortion embeddings where the distortion scales as a function of $\epsilon$, with the guarantee that for each $\epsilon$ simultaneously, the distortion of a fraction $1-\epsilon$ of all pairs is bounded accordingly. Quantitatively, we prove that any finite metric space embeds into an ultrametric with scaling distortion $O(\sqrt{1/\epsilon})$. For the graph setting, we prove that any weighted graph contains a spanning tree with scaling distortion $O(\sqrt{1/\epsilon})$. These bounds are tight even for embedding into arbitrary trees. These results imply that the average distortion of the embedding is constant and that the $\ell_2$ distortion is $O(\sqrt{\log n})$. For probabilistic embedding into spanning trees we prove a scaling distortion of $\tilde{O}(\log^2 (1/\epsilon))$, which implies constant $\ell_q$-distortion for every fixed $q<\infty$.

A major open problem in the field of metric embedding is the existence of dimension reduction for $n$-point subsets of Euclidean space, such that both distortion and dimension depend only on the doubling constant of the point set, and not on its cardinality. In this paper, we negate this possibility for $\ell_p$ spaces with $p>2$. In particular, we introduce an $n$-point subset of $\ell_p$ with doubling constant $O(1)$, and demonstrate that any embedding of the set into $\ell_p^d$ with distortion $D$ must have $D\ge\Omega((\frac{\log n}{d})^{\frac{1}{2}-\frac{1}{p}})$.

A major open problem in the field of metric embedding is the existence of dimension reduction for n-point subsets of Euclidean space, such that both distortion and dimension depend only on the doubling constant of the pointset, and not on its cardinality. In this paper, we negate this possibility for ℓp spaces with p > 2. In particular, we introduce an n-point subset of ℓp with doubling constant O(1), and demonstrate that any embedding of the set into ℓdp with distortion D must have D ≥ Ω ((c log n/d)1/2−1/p).

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 Od,ε(n log n). In this paper, we present a linear time approximation scheme for Euclidean TSP, with runtime Od,ε(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].

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.

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(Λ) + 2O(Λ log Λ)]n, and can be constructed in [2O(Λ) log3 n + ε−O(Λ) + 2O(Λ 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 2O(Λ) log n + ε−O(Λ) + 2O(Λ log Λ) update time. This is the first fully dynamic (1 + ε)-distance oracle.

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((logk)/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(nk1/t log2 k) bits, such that distance queries from any node to its k nearest neighbors can be answered with stretch O(t).

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 edge lengths.

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 ET~T[dT(u, nu)/dG(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.

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.

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 lq-distortion of a uniformly distributed pair of points. Our embedding achieves the best possible lq-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 Lp 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(log1+θ 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 Lp with nearly tight dimension. For any 1 ≤ p ≤ ⊂ and any 1 ≤ k ≤ p, we give an embedding into Lp with distortion O(⌈ log n/k ⌉) in dimension 2O(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.

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 routing problems. Lund and Yannakakis [The approximation of maximum subgraph problems, in Proceedings of the 20th International Colloquium on Automata, Languages and Programming, 1993, pp. 40-51] give inapproximability results for the problem of finding the largest vertex induced subgraph satisfying any nontrivial, hereditary property pi--e.g., independent set, planar, acyclic, bipartite. We consider the on-line version of this family of problems, where some graph G is fixed and some subgraph H of G is presented on-line, vertex by vertex. The on-line algorithm must choose a subset of the vertices of H, choosing or rejecting a vertex when it is presented, whose vertex induced subgraph satisfies property pi. Furthermore, we study the on-line version of graph coloring whose off-line version has also been shown to be inapproximable [C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, in Proceedings of the 25th ACM Symposium on Theory of Computing, 1993], on-line max edge-disjoint paths, and on-line path coloring problems. Irrespective of the time complexity, we show an Omega(n epsilon ) lower bound on the competitive ratio of randomized on-line algorithms for any of these problems. As a consequence, we obtain an Omega(n epsilon ) lower bound on the competitive ratio of randomized on-line algorithms for virtual circuit routing on general networks, in contrast to the known results for some specific networks. Similar lower bounds are obtained for on-line optical routing as well.

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.

This paper introduces a new class of mechanisms based on negotiation between market participants. This model allows us to circumvent Myerson and Satterthwaite's impossibility result and present a bilateral market mechanism that is efficient, individually rational, incentive compatible, and budget balanced in the single-unit heterogeneous setting. The underlying scheme makes this combination of desirable qualities possible by reporting a price range for each buyer-seller pair that defines a zone of possible agreements, while the final price is left open for negotiation.

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 the 25th ACM Symposium on Theory of Computing, 1993, pp. 121--129] initiated the study of such problems in a framework where distributed decision-makers must generate feasible solutions to positive linear programs with information only about local constraints. We extend their model by allowing these distributed decision-makers to perform local communication to acquire information over time and then explore the tradeoff between the amount of communication and the quality of the solution to the linear program that the decision-makers can obtain. Our main result is a distributed algorithm that obtains a $(1 + \epsilon)$ approximation to the optimal linear programming solution while using only a polylogarithmic number of rounds of local communication. This algorithm offers a significant improvement over the logarithmic approximation ratio previously obtained by Awerbuch and Azar [Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 240--249] for this problem while providing a comparable running time. Our results apply directly to the application of network flow control, an application in which distributed routers must quickly choose how to allocate bandwidth to connections using only local information to achieve global objectives. The sequential version of our algorithm is faster and considerably simpler than the best known approximation algorithms capable of achieving a $(1 + \epsilon)$ approximation ratio for positive linear programming.

Metric embedding has become a common technique in the design of algorithms. Its applicability is often dependent on how large the embedding's distortion is. For example, embedding finite metric space into trees may require linear distortion as a function of the size of the metric. Using probabilistic metric embeddings, the bound on the distortion reduces to logarithmic in the size of the metric. We make a step in the direction of bypassing the lower bound on the distortion in terms of the size of the metric. We define "multiembeddings" of metric spaces, in which a point is mapped onto a set of points, while keeping the target metric of polynomial size and preserving the distortion of paths. The distortion obtained with such multiembeddings into ultrametrics is at most $O(\log \Delta\log\log \Delta)$, where $\Delta$ is the aspect ratio of the metric. In particular, for expander graphs, we are able to obtain constant distortion embeddings into trees, in contrast with the $\Omega(\log n)$ lower bound for all previous notions of embeddings. We demonstrate the algorithmic application of the new embeddings for two optimization problems: group Steiner tree and metrical task systems.

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, firewall and security management technology is lacking. In this paper we present Firmato, a firewall management toolkit, with the following distinguishing properties and components: (1) an entity-relationship model containing, in a unified form, global knowledge of the security policy and of the network topology; (2) a model definition language, which we use as an interface to define an instance of the entity-relationship model; (3) a model compiler, translating the global knowledge of the model into firewall-specific configuration files; and (4) a graphical firewall rule illustrator. We implemented a prototype of our toolkit to work with several commercially available firewall products. This prototype was used to control an operational firewall for several months. We believe that our approach is an important step toward streamlining the process of configuring and managing firewalls, especially in complex, multi-firewall installations.

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 n1-ε 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.

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 single minded 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.

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.

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.

The k -server problem is a generalization of the paging problems, and is the most studied problem in the area of competive online problems. The Harmonic algorithm is a very natural and simple randomized algorithm for the k -server problem. We give a simple proof that the Harmonic k -server algorithm is competitive. The competitive ratio we prove is the best currently known fo the algorithm. The Harmonic algorithm is memoryless and time-efficient. This is the only such algorithm known to be competitive for the k -server problem.

We consider a version ofmultiprocessor 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 set of n jobs, with each job characterized by a processing time and a penalty. In the on-line version the jobs become available one by one and we have to schedule or reject a job before we have any information about future jobs. The objective is to minimize the makespan of the schedule for accepted jobs plus the sum of the penalties of rejected jobs. The main result is a $1+\phi\approx 2.618$ competitive algorithm for the on-line version of the problem, where $\phi$ is the golden ratio. A matching lower bound shows that this is the best possible algorithm working for all m. For fixed m we give improved bounds; in particular, for $m=2$ we give a $\phi\approx 1.618$ competitive algorithm, which is best possible. For the off-line problem we present a fully polynomial approximation scheme for fixed m and a polynomial approximation scheme for arbitrary m. Moreover, we present an approximation algorithm which runs in time $O(n\log n)$ for arbitrary m and guarantees a $2-\frac{1}{m}$ approximation ratio.

In recent years, packet filtering firewalls have seen some impressive technological advances (e.g., stateful inspection, transparency, performance, etc.) and widespread deployment. In contrast, firewall and security management technology is lacking. We present Firmato, a firewall management toolkit, with the following distinguishing properties and components: (1) an entity relationship model containing, in a unified form, global knowledge of the security policy and of the network topology; (2) a model definition language, which we use as an interface to define an instance of the entity relationship model; (3) a model compiler translating the global knowledge of the model into firewall-specific configuration files; and (4) a graphical firewall rule illustrator. We demonstrate Firmato's capabilities on a realistic example, thus showing that firewall management can be done successfully at an appropriate level of abstraction. We implemented our toolkit to work with a commercially available firewall product. We believe that our approach is an important step towards streamlining the process of configuring and managing firewalls, especially in complex, multi firewall installations.

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 each sent packet. Our objective is to develop scalable policies which provably deliver a long intact prefix of the message to each receiver at each point in time during the transmission. To accurately represent conditions in existing networks, our theoretical model of the network allows bursty periods of packet loss which can vary widely and arbitrarily over time. Under this general model, we give a proof that there is an inherent performance gap between algorithms which use encoding schemes such as forward error correction (FEC) and those which do not. We then present simple, feedback-free policies which employ FEC and have guaranteed worst-case performance. Our analytic results are complemented by trace-driven simulations which demonstrate the effectiveness of our approach in practice.

Article On approximating arbitrary metrices by tree metrics Share on Author: Yair Bartal Bell-Labs, Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJ Bell-Labs, Lucent Technologies, 600 Mountain Avenue, Murray Hill, NJView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 161–168https://doi.org/10.1145/276698.276725Published:23 May 1998 332citation1,480DownloadsMetricsTotal Citations332Total Downloads1,480Last 12 Months113Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.

We present a randomized on-line algorithm for the Metrical Tti System problem that achieves a competitive ratio of O(log6 n) for arbitrary metric spaces, against art oblivious adversary.This is the first algorithm to achieve a sublinear competitive ratio for all mernc spaces.Our algorithm uses a recent result of Bart.al[Bar96] thatan arbitrarymetric space can be probabilistically approximated by a set of metric spaces called "k-hierarchical well-separated trees" (k-HST'S).Indeed, the main technical result of this paper is an 0(}og2 n)-competitive algorithm for fl(log2 n)-HST spaces.This, combined with the result of [Bar96], yields the general bound.Note that for the k-server problem on metric spaces of k + c points our result implies a competitive ratio of O(C6 log6 k).

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.

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 online virtual circuit and optical routing problems.Lund and Yannakakis [LY93a] give inapproximability results for the problem of finding the largest vertex induced subgraph satisfying any non-trivial, hereditary, property r.E.g., independent set, planar, acyclic, bipartite, etc.We consider the on-line version of this family of problems, where some graph G is fixed and some subgraph H is presented on-line, vertex by vertex.The on-line algorithm must choose a subset of the vertices of i7, choosing or rejecting a vertex when it is presented, whose vertex induced subgraph satisfies property m.Furthermore, we study the on-line version line algorithms for any of these problems.As a consequence, we obtain an fl(n') lower bound on the competitive ratio of randomized on-line algorithms for virtual circuit routing on general networks, in contrast to the known results for some specific networks.Moreover, this lower bound holds even if the use of preemption is allowed.Similar lower bounds are obtained for on-line optical routing as well,

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.>

Article Competitive distributed file allocation Share on Authors: Baruch Awerbuch View Profile , Yair Bartal View Profile , Amos Fiat View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 164–173https://doi.org/10.1145/167088.167142Online:01 June 1993Publication History 82citation483DownloadsMetricsTotal Citations82Total Downloads483Last 12 Months10Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.>

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 make span, the completion time of the last job. In the on-line version, as soon as job j arrives, it must be assigned immediately to one of the m machines.

We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([C], [DF], [ML]), where copies of a file may be stored in the local storage of some subset of processors, copies may be replicated and discarded over time so as to optimize communication costs, but multiple copies must be kept consistent and at least one copy must be stored somewhere in the network at all times. We deal with competitive algorithms for minimizing communication costs, over arbitrary sequences of reads and writes, and arbitrary network topologies. We define the constrained file allocation problem to be the solution of many individual file allocation problems simultaneously, subject to the constraints of local memory size. We give competitive algorithms for this prblem on uniform networks. We then introduce distributed competitive algorithms for on-line data tracking (a generalization of mobile user tracking [AP1, AP3] to transform our competitive distributed data management algorithms into distributed algorithms themselves.