Distributed algorithms for covering, packing and maximum weighted matching
From MaRDI portal
Publication:661048
DOI10.1007/s00446-011-0127-7zbMath1231.68276arXiv2005.13628OpenAlexW1970155114MaRDI QIDQ661048
Neal E. Young, Christos Koufogiannakis
Publication date: 6 February 2012
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2005.13628
Mixed integer programming (90C11) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)
Related Items
Improved deterministic distributed matching via rounding ⋮ Optimal distributed covering algorithms ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Distributed backup placement in networks ⋮ Parallel approximation for partial set cover ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Efficient Approximation Algorithms for Weighted $b$-Matching ⋮ Set cover problems with small neighborhood covers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed approximation of capacitated dominating sets
- Approximating weighted matchings in parallel
- Efficient bounds for the stable set, vertex cover and set packing problems
- A fast and simple randomized parallel algorithm for maximal matching
- A fast approximation algorithm for the multicovering problem
- On the ratio of optimal integral and fractional covers
- Low diameter graph decompositions
- An optimal parallel algorithm for maximal matching
- A fast and efficient NC algorithm for maximal matching
- Rounding algorithms for covering problems
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Approximation algorithms for covering/packing integer programs
- On the Distributed Complexity of Computing Maximal Matchings
- Improved Distributed Approximate Matching
- Fast Distributed Approximations in Planar Graphs
- On k-Column Sparse Packing Programs
- The price of being near-sighted
- A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
- Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- Approximability of Sparse Integer Programs
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- A Greedy Heuristic for the Set-Covering Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Locality in Distributed Graph Algorithms
- A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers
- Probabilistic recurrence relations
- Distributed Computing: A Locality-Sensitive Approach
- What Can be Computed Locally?
- On the Complexity of Distributed Network Decomposition
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Distributed and parallel algorithms for weighted vertex cover and other covering problems
- Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
- Paths, Trees, and Flowers
- Distributed approximate matching
- A memetic algorithm to schedule planned maintenance for the national grid
- Distributed Weighted Matching
- Algorithms – ESA 2004
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- What cannot be computed locally!
- Computing and Combinatorics
- Constant-time distributed dominating set approximation
