The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
From MaRDI portal
Publication:6202219
DOI10.1145/3583668.3594562arXiv2305.01324OpenAlexW4380881055MaRDI QIDQ6202219
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
Cites Work
- Unnamed Item
- Unnamed Item
- Distributed minimum dominating set approximations in restricted families of graphs
- Distributed algorithms for weighted problems in sparse graphs
- Low diameter graph decompositions
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
- Property testing of planarity in the \textsf{CONGEST} model
- Lower bounds for local approximation
- Improved Distributed Approximate Matching
- Local Computation
- Fast Distributed Approximations in Planar Graphs
- Distributed Approximate Matching
- Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
- Locality in Distributed Graph Algorithms
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
- Distributed Dominating Set Approximations beyond Planar Graphs
- On the complexity of local distributed graph problems
- Fast Distributed Approximation for Max-Cut
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
- Optimal Distributed Covering Algorithms
- Hardness of Distributed Optimization
- The Energy Complexity of Broadcast
- Deterministic distributed edge-coloring with fewer colors
- Distributed Maximal Independent Set using Small Messages
- Brief Announcement
- Distributed Strong Diameter Network Decomposition
- A Faster Distributed Radio Broadcast Primitive
- Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
- Distributed Approximation of Maximum Independent Set and Maximum Matching
- Distributed Almost Exact Approximations for Minor-Closed Families
- On Distributed Listing of Cliques
- The Energy Complexity of BFS in Radio Networks
This page was built for publication: The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs