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

DOI10.1145/3583668.3594562arXiv2305.01324OpenAlexW4380881055WikidataQ130816751 ScholiaQ130816751MaRDI QIDQ6202219FDOQ6202219

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)

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.

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)

Cites Work

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

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)