Distributed algorithms for covering, packing and maximum weighted matching
From MaRDI portal
Publication:661048
Abstract: This paper gives poly-logarithmic-round, distributed D-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio D is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with D=2). Via duality, the paper also gives poly-logarithmic-round, distributed D-approximation algorithms for Fractional Packing linear programs (where D is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where D is the maximum size of any of the hyperedges; for graphs D=2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms.
Recommendations
- Distributed and parallel algorithms for weighted vertex cover and other covering problems
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- Optimal distributed covering algorithms
- Computing and Combinatorics
- Distributed weighted vertex cover via maximal matchings
Cites work
- A fast and efficient NC algorithm for maximal matching
- A fast and simple randomized parallel algorithm for maximal matching
- A fast approximation algorithm for the multicovering problem
- A Greedy Heuristic for the Set-Covering Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- A memetic algorithm to schedule planned maintenance for the national grid
- A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
- A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers
- Algorithms – ESA 2004
- An optimal parallel algorithm for maximal matching
- Approximability of Sparse Integer Programs
- Approximating weighted matchings in parallel
- Approximation algorithms for covering/packing integer programs
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Computing and Combinatorics
- Constant-time distributed dominating set approximation
- Distributed and parallel algorithms for weighted vertex cover and other covering problems
- Distributed approximate matching
- Distributed approximation of capacitated dominating sets
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- Distributed Weighted Matching
- Efficient bounds for the stable set, vertex cover and set packing problems
- Fast Distributed Approximations in Planar Graphs
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- scientific article; zbMATH DE number 3869066 (Why is no real title available?)
- scientific article; zbMATH DE number 3495588 (Why is no real title available?)
- scientific article; zbMATH DE number 1759463 (Why is no real title available?)
- scientific article; zbMATH DE number 1445293 (Why is no real title available?)
- scientific article; zbMATH DE number 3409134 (Why is no real title available?)
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Improved Distributed Approximate Matching
- Locality in Distributed Graph Algorithms
- Low diameter graph decompositions
- New approaches to covering and packing problems
- On k-column sparse packing programs
- On the Complexity of Distributed Network Decomposition
- On the distributed complexity of computing maximal matchings
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- On the ratio of optimal integral and fractional covers
- Paths, Trees, and Flowers
- Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
- Probabilistic recurrence relations
- Rounding algorithms for covering problems
- The price of being near-sighted
- What Can be Computed Locally?
- What cannot be computed locally!
Cited in
(15)- Distributed backup placement in networks
- Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
- Improved deterministic distributed matching via rounding
- Parallel approximation for partial set cover
- Set cover problems with small neighborhood covers
- Optimal distributed covering algorithms
- Efficient approximation algorithms for weighted b-matching
- Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- Tight bounds on the round complexity of the distributed maximum coverage problem
- Distributed set cover approximation: primal-dual with optimal locality
- Fair packing and covering on a relative scale
- Distributed and parallel algorithms for weighted vertex cover and other covering problems
- Approximation algorithms in combinatorial scientific computing
- Towards distributed two-stage stochastic optimization
This page was built for publication: Distributed algorithms for covering, packing and maximum weighted matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q661048)
