Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHardness of Distributed Optimization
91
0
0.0
(
0
)
Added by
Michal Dory
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper studies lower bounds for fundamental optimization problems in the CONGEST model. We show that solving problems exactly in this model can be a hard task, by providing $tilde{Omega}(n^2)$ lower bounds for cornerstone problems, such as minimum dominating set (MDS), Hamiltonian path, Steiner tree and max-cut. These are almost tight, since all of these problems can be solved optimally in $O(n^2)$ rounds. Moreover, we show that even in bounded-degree graphs and even in simple graphs with maximum degree 5 and logarithmic diameter, it holds that various tasks, such as finding a maximum independent set (MaxIS) or a minimum vertex cover, are still difficult, requiring a near-tight number of $tilde{Omega}(n)$ rounds. Furthermore, we show that in some cases even approximations are difficult, by providing an $tilde{Omega}(n^2)$ lower bound for a $(7/8+epsilon)$-approximation for MaxIS, and a nearly-linear lower bound for an $O(log{n})$-approximation for the $k$-MDS problem for any constant $k geq 2$, as well as for several variants of the Steiner tree problem. Our lower bounds are based on a rich variety of constructions that leverage novel observations, and reductions among problems that are specialized for the CONGEST model. However, for several additional approximation problems, as well as for exact computation of some central problems in $P$, such as maximum matching and max flow, we show that such constructions cannot be designed, by which we exemplify some limitations of this framework.
rate research
Read More
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 (Kuhn et al.~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 $O( (D/epsilon) log n)$ rounds in the $mathcal{LOCAL}$ model and finds a $(1+epsilon)$-approximation to the optimal LP solution for any $0 < epsilon leq 1$, where $D$ 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 $3$- and $4$-Spanner, Directed $k$-Spanner, Lowest Degree $k$-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.
We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and hardness results. Our main hardness result shows that an $alpha$-approximation for the minimum directed $k$-spanner problem for $k geq 5$ requires $Omega(n /sqrt{alpha}log{n})$ rounds using deterministic algorithms or $Omega(sqrt{n }/sqrt{alpha}log{n})$ rounds using randomized ones, in the CONGEST model of distributed computing. Combined with the constant-round $O(n^{epsilon})$-approximation algorithm in the LOCAL model of [Barenboim, Elkin and Gavoille, 2016], as well as a polylog-round $(1+epsilon)$-approximation algorithm in the LOCAL model that we show here, our lower bounds for the CONGEST model imply a strict separation between the LOCAL and CONGEST models. Notably, to the best of our knowledge, this is the first separation between these models for a local approximation problem. Similarly, a separation between the directed and undirected cases is implied. We also prove a nearly-linear lower bound for the minimum weighted $k$-spanner problem for $k geq 4$, and we show lower bounds for the weighted 2-spanner problem. On the algorithmic side, apart from the aforementioned $(1+epsilon)$-approximation algorithm for minimum $k$-spanners, our main contribution is a new distributed construction of minimum 2-spanners that uses only polynomial local computations. Our algorithm has a guaranteed approximation ratio of $O(log(m/n))$ for a graph with $n$ vertices and $m$ edges, which matches the best known ratio for polynomial time sequential algorithms [Kortsarz and Peleg, 1994], and is tight if we restrict ourselves to polynomial local computations. Our approach allows us to extend our algorithm to work also for the directed, weighted, and client-server variants of the problem.
We present a randomized distributed algorithm that computes a $Delta$-coloring in any non-complete graph with maximum degree $Delta geq 4$ in $O(log Delta) + 2^{O(sqrt{loglog n})}$ rounds, as well as a randomized algorithm that computes a $Delta$-coloring in $O((log log n)^2)$ rounds when $Delta in [3, O(1)]$. Both these algorithms improve on an $O(log^3 n/log Delta)$-round algorithm of Panconesi and Srinivasan~[STOC1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an $Omega(loglog n)$ round lower bound of Brandt et al.~[STOC16].
Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most research has dealt with the decision problem of whether a reconfiguration schedule exists, and the complexity of finding one. A prime example is the reconfiguration of vertex covers. We initiate the study of batched vertex cover reconfiguration, which allows to reconfigure multiple vertices concurrently while requiring that any adversarial reconfiguration order within a batch maintains feasibility. The latter provides robustness, e.g., if the simultaneous reconfiguration of a batch cannot be guaranteed. The quality of a schedule is measured by the number of batches until all nodes are reconfigured, and its cost, i.e., the maximum size of an intermediate vertex cover. To set a baseline for batch reconfiguration, we show that for graphs belonging to one of the classes ${mathsf{cycles, trees, forests, chordal, cactus, eventext{-}holetext{-}free, clawtext{-}free}}$, there are schedules that use $O(varepsilon^{-1})$ batches and incur only a $1+varepsilon$ multiplicative increase in cost over the best sequential schedules. Our main contribution is to compute such batch schedules in $O(varepsilon^{-1}log^* n)$ distributed time, which we also show to be tight. Further, we show that once we step out of these graph classes we face a very different situation. There are graph classes on which no efficient distributed algorithm can obtain the best (or almost best) existing schedule. Moreover, there are classes of bounded degree graphs which do not admit any reconfiguration schedules without incurring a large multiplicative increase in the cost at all.
This document is an informal bibliography of the papers dealing with distributed approximation algorithms. A classic setting for such algorithms is bounded degree graphs, but there is a whole set of techniques that have been developed for other classes. These later classes are the focus of the current work. These classes have a geometric nature (planar, bounded genus and unit-disk graphs) and/or have bounded parameters (arboricity, expansion, growth, independence) or forbidden structures (forbidden minors).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
