The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs

DOI10.1145/3583668.3594562MaRDI QIDQ6202219OpenAlexWikidataFDO

Authors Yi-Jun Chang, Zeyong Li

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.01324

zbMATH Keywords

low-diameter decompositiondistributed approximationLOCAL model

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: In this paper, we present a low-diameter decomposition algorithm in the LOCAL model of distributed computing that succeeds with probability $1-1/poly(n)$. Specifically, we show how to compute an $left(epsilon,Oleft(fraclognepsilonight)ight)$ low-diameter decomposition in $Oleft(fraclo{g}^3(1/epsilon)lognepsilonight)$ round Further developing our techniques, we show new distributed algorithms for approximating general packing and covering integer linear programs in the LOCAL model. For packing problems, our algorithm finds an $(1-epsilon)$-approximate solution in $Oleft(fraclo{g}^3(1/epsilon)lognepsilonight)$ rounds with probability $1-1/poly(n)$. For covering problems, our algorithm finds an $(1+epsilon)$-approximate solution in $Oleft(fracleft(loglogn+log(1/epsilon)ight{)}^{3}lognepsilonight)$ rounds with probability $1-1/poly(n)$. These results improve upon the previous $Oleft(fraclo{g}^{3}nepsilonight)$-round algorithm by Ghaffari, Kuhn, and Maus [STOC 2017] which is based on network decompositions. Our algorithms are near-optimal for many fundamental combinatorial graph optimization problems in the LOCAL model, such as minimum vertex cover and minimum dominating set, as their $(1pmepsilon)$-approximate solutions require $Omegaleft(fraclognepsilonight)$ rounds to compute.

Cites work

• scientific article; zbMATH DE number 1833421 (Why is no real title available?)
• scientific article; zbMATH DE number 7650908 (Why is no real title available?)
• A Faster Distributed Radio Broadcast Primitive
• Brief Announcement
• Deterministic distributed edge-coloring with fewer colors
• Distributed Almost Exact Approximations for Minor-Closed Families
• Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
• Distributed Dominating Set Approximations beyond Planar Graphs
• Distributed Maximal Independent Set using Small Messages
• Distributed Strong Diameter Network Decomposition
• Distributed algorithms for weighted problems in sparse graphs
• Distributed approximate matching
• Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
• Distributed approximation of maximum independent set and maximum matching
• Distributed minimum dominating set approximations in restricted families of graphs
• Efficient algorithms for constructing very sparse spanners and emulators
• Exploiting spontaneous transmissions for broadcasting and leader election in radio networks
• Fast Distributed Approximation for Max-Cut
• Fast Distributed Approximations in Planar Graphs
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Hardness of Distributed Optimization
• Improved Distributed Approximate Matching
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond
• Local computation: lower and upper bounds
• Locality in Distributed Graph Algorithms
• Low diameter graph decompositions
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• On Distributed Listing of Cliques
• On the complexity of local distributed graph problems
• Optimal Distributed Covering Algorithms
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Property testing of planarity in the \textsf{CONGEST} model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• The Energy Complexity of BFS in Radio Networks
• The energy complexity of broadcast
• Three notes on distributed property testing

This page was built for publication: The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202219)