A parallel algorithm for minimum weight set cover with small neighborhood property
Yingli Ran, Yaoyao Zhang, Zhao Zhang · arXiv (Cornell University) · 2022
This paper studies the minimum weight set cover (MinWSC) problem with a {\em small neighborhood cover} (SNC) property proposed by Agarwal {\it et al.} in \cite{Agarwal.}. A parallel algorithm for MinWSC with $τ$-SNC property is presented, obtaining approximation ratio $τ(1+3\varepsilon)$ in $O(L\log_{1+\varepsilon}\frac{n^3}{\varepsilon^2}+ 4τ^{3}2^τL^2\log n)$ rounds, where $0< \varepsilon