Back to Search
Start Over
Distributed algorithms for covering, packing and maximum weighted matching
- Source :
- Distributed Computing, vol 24, iss 1
- Publication Year :
- 2011
- Publisher :
- eScholarship, University of California, 2011.
-
Abstract
- This paper gives poly-logarithmic-round, distributed δ-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio δ is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with δ = 2). Via duality, the paper also gives poly-logarithmic-round, distributed δ-approximation algorithms for Fractional Packing linear programs (where δ is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where δ is the maximum size of any of the hyperedges; for graphs δ = 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. © 2011 Springer-Verlag.
- Subjects :
- FOS: Computer and information sciences
cs.DC
Computer Networks and Communications
G.1.6
Vertex cover
Duality (optimization)
Packing and covering
0102 computer and information sciences
01 natural sciences
Theoretical Computer Science
Submodular set function
90C26
Computation Theory & Mathematics
Combinatorics
68W15
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
Computer Science - Data Structures and Algorithms
C.2.4
Matching
Data Structures and Algorithms (cs.DS)
Maximum size
0101 mathematics
Mathematics
90C26, 68W15
010102 general mathematics
Covering problems
TheoryofComputation_GENERAL
Approximation algorithms
Monotone polygon
Integer linear programming
cs.DS
Computer Science - Distributed, Parallel, and Cluster Computing
Computational Theory and Mathematics
010201 computation theory & mathematics
Hardware and Architecture
Distributed algorithm
Distributed, Parallel, and Cluster Computing (cs.DC)
Distributed Computing
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Distributed Computing, vol 24, iss 1
- Accession number :
- edsair.doi.dedup.....966c3c225ba1850c7b7a1626c021d743