Ben-Basat, Ran;
Even, Guy;
Kawarabayashi, Ken-ichi;
Schwartzman, Gregory;
(2021)
Optimal distributed covering algorithms.
Distributed Computing
10.1007/s00446-021-00391-w.
(In press).
Preview |
PDF
Ben-Basat2021_Article_OptimalDistributedCoveringAlgo.pdf - Published Version Download (334kB) | Preview |
Abstract
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is (f+ε). Let Δ denote the maximum degree in the hypergraph. Our algorithm runs in the CONGEST model and requires O(logΔ/loglogΔ) rounds, for constants ε∈(0,1] and f∈N+. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and ε, our algorithm improves over the (f+ε)-approximation algorithm of Kuhn et al. (SODA, 2006)whose running time is O(logΔ+logW), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in O(flogn) rounds, improving over the classical result of Khuller et al. (J Algorithms, 1994) that achieves a running time of O(flog2n). Finally, for weighted vertex cover (f=2) our algorithm achieves a deterministic running time of O(logn), matching the randomized previously best result of Koufogiannakis and Young (Distrib Comput, 2011). We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (f⌈log2(M)+1⌉+ε)-approximate integral solution in O((1+f/logn)⋅(logΔloglogΔ+(f⋅logM)1.01⋅logε−1⋅(logΔ)0.01)) rounds, where f bounds the number of variables in a constraint, Δ bounds the number of constraints a variable appears in, and M=max{1,⌈1/amin⌉}, where amin is the smallest normalized constraint coefficient.
| Type: | Article |
|---|---|
| Title: | Optimal distributed covering algorithms |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s00446-021-00391-w |
| Publisher version: | https://doi.org/10.1007/s00446-021-00391-w |
| Language: | English |
| Additional information: | This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10152072 |
Archive Staff Only
 |
View Item |
