Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistributed Weighted Min-Cut in Nearly-Optimal Time
156
0
0.0
(
0
)
Added by
Sagnik Mukhopadhyay
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Minimum-weight cut (min-cut) is a basic measure of a networks connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC13; Nanongkai, Su, DISC14]) can guarantee a solution that is $(1+epsilon)$-approximation at best while the exact $tilde O(n^{0.8}D^{0.2} + n^{0.9})$-time algorithm [Ghaffari, Nowicki, Thorup, SODA20] works only on *simple* networks (no weights and no parallel edges). Here $n$ and $D$ denote the networks number of vertices and hop-diameter, respectively. For the weighted case, the best bound was $tilde O(n)$ [Daga, Henzinger, Nanongkai, Saranurak, STOC19]. In this paper, we provide an *exact* $tilde O(sqrt n + D)$-time algorithm for computing min-cut on *weighted* networks. Our result improves even the previous algorithm that works only on simple networks. Its time complexity matches the known lower bound up to polylogarithmic factors. At the heart of our algorithm are a clever routing trick and two structural lemmas regarding the structure of a minimum cut of a graph. These two structural lemmas considerably strengthen and generalize the framework of Mukhopadhyay-Nanongkai [STOC20] and can be of independent interest.
rate research
Read More
Consider the following 2-respecting min-cut problem. Given a weighted graph $G$ and its spanning tree $T$, find the minimum cut among the cuts that contain at most two edges in $T$. This problem is an important subroutine in Kargers celebrated randomized near-linear-time min-cut algorithm [STOC96]. We present a new approach for this problem which can be easily implemented in many settings, leading to the following randomized min-cut algorithms for weighted graphs. * An $O(mfrac{log^2 n}{loglog n} + nlog^6 n)$-time sequential algorithm: This improves Kargers $O(m log^3 n)$ and $O(mfrac{(log^2 n)log (n^2/m)}{loglog n} + nlog^6 n)$ bounds when the input graph is not extremely sparse or dense. Improvements over Kargers bounds were previously known only under a rather strong assumption that the input graph is simple [Henzinger et al. SODA17; Ghaffari et al. SODA20]. For unweighted graphs with parallel edges, our bound can be improved to $O(mfrac{log^{1.5} n}{loglog n} + nlog^6 n)$. * An algorithm requiring $tilde O(n)$ cut queries to compute the min-cut of a weighted graph: This answers an open problem by Rubinstein et al. ITCS18, who obtained a similar bound for simple graphs. * A streaming algorithm that requires $tilde O(n)$ space and $O(log n)$ passes to compute the min-cut: The only previous non-trivial exact min-cut algorithm in this setting is the 2-pass $tilde O(n)$-space algorithm on simple graphs [Rubinstein et al., ITCS18] (observed by Assadi et al. STOC19). In contrast to Kargers 2-respecting min-cut algorithm which deploys sophisticated dynamic programming techniques, our approach exploits some cute structural properties so that it only needs to compute the values of $tilde O(n)$ cuts corresponding to removing $tilde O(n)$ pairs of tree edges, an operation that can be done quickly in many settings.
An $(epsilon,phi)$-expander decomposition of a graph $G=(V,E)$ is a clustering of the vertices $V=V_{1}cupcdotscup V_{x}$ such that (1) each cluster $V_{i}$ induces subgraph with conductance at least $phi$, and (2) the number of inter-cluster edges is at most $epsilon|E|$. In this paper, we give an improved distributed expander decomposition. Specifically, we construct an $(epsilon,phi)$-expander decomposition with $phi=(epsilon/log n)^{2^{O(k)}}$ in $O(n^{2/k}cdottext{poly}(1/phi,log n))$ rounds for any $epsilonin(0,1)$ and positive integer $k$. For example, a $(0.01,1/text{poly}log n)$-expander decomposition can be computed in $O(n^{gamma})$ rounds, for any arbitrarily small constant $gamma>0$. Previously, the algorithm by Chang, Pettie, and Zhang can construct a $(1/6,1/text{poly}log n)$-expander decomposition using $tilde{O}(n^{1-delta})$ rounds for any $delta>0$, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which forms a subgraph with arboricity at most $n^{delta}$. Our algorithm does not have this caveat. By slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC17], we obtain a triangle enumeration algorithm using $tilde{O}(n^{1/3})$ rounds. This matches the lower bound by Izumi and Le Gall [PODC17] and Pandurangan, Robinson and Scquizzato [SPAA18] of $tilde{Omega}(n^{1/3})$ which holds even in the CONGESTED CLIQUE model. This provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED CLIQUE. The key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.
We give an $n^{2+o(1)}$-time algorithm for finding $s$-$t$ min-cuts for all pairs of vertices $s$ and $t$ in a simple, undirected graph on $n$ vertices. We do so by constructing a Gomory-Hu tree (or cut equivalent tree) in the same running time, thereby improving on the recent bound of $tilde{O}(n^{2.5})$ by Abboud et al. (FOCS 2021). Our running time is nearly optimal as a function of $n$.
This paper gives poly-logarithmic-round, distributed D-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio D is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with D=2). Via duality, the paper also gives poly-logarithmic-round, distributed D-approximation algorithms for Fractional Packing linear programs (where D is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where D is the maximum size of any of the hyperedges; for graphs D=2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms.
In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constraint. The adaptivity of an algorithm is the number of sequential rounds of queries it makes to the evaluation oracle of the function, where in every round the algorithm is allowed to make polynomially-many parallel queries. Adaptivity is an important consideration in settings where the objective function is estimated using samples and in applications where adaptivity is the main running time bottleneck. Previous algorithms achieving a nearly-optimal $1 - 1/e - epsilon$ approximation require $Omega(n)$ rounds of adaptivity. In this work, we give the first algorithm that achieves a $1 - 1/e - epsilon$ approximation using $O(ln{n} / epsilon^2)$ rounds of adaptivity. The number of function evaluations and additional running time of the algorithm are $O(n mathrm{poly}(log{n}, 1/epsilon))$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
