Summary: This paper presents a deterministic distributed algorithm for computing an \(f(1+\varepsilon)\) approximation of the well-studied minimum set cover problem, for any constant \(\varepsilon>0\), in \(O(\log(f\Delta)/\log\log f\Delta))\) rounds. Here, \(f\) denotes the maximum element frequency and \(\Delta\) denotes the cardinality of the largest set. This \(f(1+\varepsilon)\) approximation almost matches the \(f\)-approximation guarantee of standard centralized primal-dual algorithms, which is known to be essentially the best possible approximation for polynomial-time computations. The round complexity almost matches the \(\Omega(\log(\Delta)/\log\log(\Delta))\) lower bound by F. Kuhn et al. [J. ACM 63, No. 2, Paper No. 17, 44 p. (2016; Zbl 1426.68092)], which holds for even \(f=2\) and for any \(\operatorname{poly}(\log\Delta)\) approximation. Our algorithm also gives an alternative way to reproduce the time-optimal \(2(1+\varepsilon)\)-approximation of vertex cover, with round complexity \(O(\log\Delta/\log\log\Delta)\), as presented by R. Bar-Yehuda et al. [J. ACM 64, No. 3, Article No. 23, 11 p. (2017; Zbl 1426.68291)] for weighted vertex cover. Our method is quite different and it can be viewed as a locality-optimal way of performing primal-dual for the more general case of set cover. We note that the vertex cover algorithm of Bar-Yehuda et al. [loc. cit.] does not extend to set cover (when \(f\ge 3\)).
For the entire collection see [Zbl 1423.68037].