caa a22 4500 44535500X CHVBK 20180317142857.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00446-011-0127-7 doi (NATIONALLICENCE)springer-10.1007/s00446-011-0127-7 Distributed algorithms for covering, packing and maximum weighted matching [Elektronische Daten] [Christos Koufogiannakis, Neal Young] 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. Springer-Verlag, 2011 Approximation algorithms nationallicence Integer linear programming nationallicence Packing and covering nationallicence Vertex cover nationallicence Matching nationallicence Koufogiannakis Christos Department of Computer Science and Engineering, University of California, Riverside, CA, USA aut Young Neal Department of Computer Science and Engineering, University of California, Riverside, CA, USA aut Distributed Computing Springer-Verlag 24/1(2011-09-01), 45-63 0178-2770 24:1<45 2011 24 446 https://doi.org/10.1007/s00446-011-0127-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0127-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Koufogiannakis Christos Department of Computer Science and Engineering, University of California, Riverside, CA, USA aut NATIONALLICENCE 700 1- Young Neal Department of Computer Science and Engineering, University of California, Riverside, CA, USA aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/1(2011-09-01), 45-63 0178-2770 24:1<45 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer