Optimal Distributed Covering Algorithms

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+ϵ)$. Our algorithm runs in the CONGEST model and requires $O(\log \mathrm{\Delta }\mathrm{/}\log \log \mathrm{\Delta })$ rounds, for constants $ϵ\in (0,1]$ and $f\in 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. For constant values of $f$ and $ϵ$, our algorithm improves over the $(f+ϵ)$-approximation algorithm of KMW06 whose running time is $O(\log \mathrm{\Delta }+\log W)$, 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(f\log n)$ rounds, improving over the classical result of KVY94 that achieves a running time of $O(f{\log }^{2}n)$. Finally, for weighted vertex cover ($f=2$) our algorithm achieves a \emph{deterministic} running time of $O(\log n)$, matching the \emph{randomized} previously best result of KY11. 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+ϵ)$-approximate integral solution in $O(\frac{\log\Delta}{\log\log\Delta}+(f\cdot\log M)^{1.01}\log\epsilon^{-1}(\log\Delta)^{0.01})$rounds,where$f$ bounds the number of variables in a constraint, $\mathrm{\Delta }$ bounds the number of constraints a variable appears in, and $M=\max \{1,1\mathrm{/}{a}_{\min }\}$, where $a_{min}$ is the smallest normalized constraint coefficient. This improves over the results of KMW06 for the integral case, which runs in $O(\epsilon^{-4}\cdot f^4\cdot \log f\cdot\log(M\cdot\Delta))$ rounds.