Solving linear programs is often a challenging task in distributed settings. While there are good algorithms for solving packing and covering linear programs in a distributed manner ( 2006), this is essentially the only class of linear programs for which such an algorithm is known. In this work we provide a distributed algorithm for solving a different class of convex programs which we call "distance-bounded network design convex programs". These can be thought of as relaxations of network design problems in which the connectivity requirement includes a distance constraint (most notably, graph spanners). Our algorithm runs in @math rounds in the @math model and finds a @math -approximation to the optimal LP solution for any @math , where @math is the largest distance constraint. While solving linear programs in a distributed setting is interesting in its own right, this class of convex programs is particularly important because solving them is often a crucial step when designing approximation algorithms. Hence we almost immediately obtain new and improved distributed approximation algorithms for a variety of network design problems, including Basic @math - and @math -Spanner, Directed @math -Spanner, Lowest Degree @math -Spanner, and Shallow-Light Steiner Network Design with a spanning demand graph. Our algorithms do not require any "heavy" computation and essentially match the best-known centralized approximation algorithms, while previous approaches which do not use heavy computation give approximations which are worse than the best-known centralized bounds.
A special case of our result was proved earlier in @cite_1 , who showed how to solve the LP relaxation of [2] in the model in @math rounds (they actually show more than this, by giving a distributed algorithm for the version of [2], but that is not germane to our results). Our techniques are heavily based on @cite_1 , which is itself based on the ideas from @cite_19 . In particular, @cite_19 uses a Linial-Saks decomposition @cite_5 to solve local'' versions of the linear program in different parts of the graph, and then combines these appropriately. To make this work for the [2] LP relaxation, @cite_1 had to use , which can be thought of as a variant of Linial-Saks with slightly different guarantees which, for technical reasons, are more useful for network design LPs. In this paper we extend these techniques further by giving a more general definition of padded decomposition which works for larger distance requirements, showing how to construct them in the model, and then showing that the basic combining'' idea from @cite_1 can be extended to handle these more general decompositions and far more general constraints and objective functions.
@cite_19 @cite_5 @cite_1
2092349993 1961231572 2038964811 2487418934
Chapter 36 Decomposing Graphs into Regions of Small Diameter* Nathan Linialt Michael .lss A decomposition of a graph G = (V, E) is a partition of the vertex set into subsets (called lhks). The diameter of a decomposition is the least. d such that any two vertices belonging to the same connected component of a block are at distance < d. In this paper we prove (nearly best possible) statements of the form: .4ny n–vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [AGLP1 it was shown that every graph has a decomposition into at most s(n) blocks of diameter at most s(n) for s(n) = o( loglog d h n). usinga,technique of Awerbuch [A] and Awerbuch and Peleg [AP], we improve this result by showing that every graph has a decomposition of diameter ()(log n) into O(log n) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in time 0(log2 n). The construction can be parametrized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible for two families of graphs the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner’s lemma for the first class and Tucker’s lemma for the second. *This work was supported in part by NSF contracts DMS87-03541 and CCR-8911388 tDepartment of Computer Science, Hebrew University, Jerusalem, Israel. + ‘Department of Computer Science and Engineering, Mail Code C-014, University of California, San Diego, La Jolla, CA 92093-0114. We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate these problems from the point of view of two possible generalizations: as Min-CSPs, and as Submodular Multiway Partition problems. These two generalizations lead to two natural relaxations that we call respectively the Local Distribution LP, and the Lovasz relaxation. The Local Distribution LP is generally stronger than the Lovasz relaxation, but applicable only to Min-CSP with predicates of constant size. The relaxations coincide in some cases such as Multiway Cut where they are both equivalent to the CKR relaxation. We show that the Lovasz relaxation gives a (2--2 k)-approximation for Submodular Multiway Partition with k terminals, improving a recent 2-approximation [2]. We prove that this factor is optimal in two senses: (1) A (2--2 k -- e)-approximation for Submodular Multiway Partition with k terminals would require exponentially many value queries (in the oracle model), or imply NP = RP (for certain explicit submodular functions). (2) For Hypergraph Multiway Cut and Node-weighted Multiway Cut with k terminals, both special cases of Submodular Multiway Partition, we prove that a (2--2 k -- e)-approximation is NP-hard, assuming the Unique Games Conjecture. Both our hardness results are more general: (1) We show that the notion of symmetry gap, previously used for submodular maximization problems [19, 6], also implies hardness results for submodular minimization problems. (2) Assuming the Unique Games Conjecture, we show that the Local Distribution LP gives an optimal approximation for every Min-CSP that includes the Not-Equal predicate. Finally, we connect the two hardness techniques by proving that the integrality gap of the Local Distribution LP coincides with the symmetry gap of the multilinear relaxation (for a related instance). This shows that the appearance of the same hardness threshold for a Min-CSP and the related submodular minimization problem is not a coincidence. In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of [SIAM J. Comput. , 23 (1994), pp. 864--894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14--23]. We present approximation algorithms for 0-Extension . In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 (1998), pp. 71--101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [SIAM J. Comput. , 25 (1996), pp. 235--251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least @math for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations. Abstract A partition ( C 1 , C 2 , … , C q ) of G = ( V , E ) into clusters of strong (respectively, weak) diameter d , such that the supergraph obtained by contracting each C i is l -colorable is called a strong (resp., weak) ( d , l ) -network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. showed that strong ( d , l ) -network-decompositions with d = l = exp ⁡ O ( log ⁡ n log ⁡ log ⁡ n ) can be computed in distributed deterministic time O ( d ) . Even more importantly, they demonstrated that network-decompositions can be used for a great variety of applications in the message-passing model of distributed computing. The result of was improved by Panconesi and Srinivasan in 1992: in the latter result d = l = exp ⁡ O ( log ⁡ n ) , and the running time is O ( d ) as well. In another remarkable breakthrough Linial and Saks (in 1992) showed that weak ( O ( log ⁡ n ) , O ( log ⁡ n ) ) -network-decompositions can be computed in distributed randomized time O ( log 2 ⁡ n ) . Much more recently Barenboim (2012) devised a distributed randomized constant-time algorithm for computing strong network decompositions with d = O ( 1 ) . However, the parameter l in his result is O ( n 1 2 + ϵ ) . In this paper we drastically improve the result of Barenboim and devise a distributed randomized constant-time algorithm for computing strong ( O ( 1 ) , O ( n ϵ ) ) -network-decompositions. As a corollary we derive a constant-time randomized O ( n ϵ ) -approximation algorithm for the distributed minimum coloring problem, improving the previously best-known O ( n 1 2 + ϵ ) approximation guarantee. We also derive other improved distributed algorithms for a variety of problems. Most notably, for the extremely well-studied distributed minimum dominating set problem currently there is no known deterministic polylogarithmic-time algorithm. We devise a deterministic polylogarithmic-time approximation algorithm for this problem, addressing an open problem of Lenzen and Wattenhofer (2010).