@article {IOPORT.05865589,
    author       = {Levin, Asaf and Yovel, Uri},
    title        = {Uniform unweighted set cover: the power of non-oblivious local search.},
    year         = {2011},
    journal      = {Theoretical Computer Science},
    volume       = {412},
    number       = {12-14},
    issn         = {0304-3975},
    pages        = {1033-1053},
    publisher    = {Elsevier Science Publishers, Amsterdam},
    doi          = {10.1016/j.tcs.2010.12.004},
    abstract     = {Summary: We are given $n$ base elements and a finite collection of subsets of them. The size of any subset lies between $p$ and $k$ $(p<k)$. In addition, we assume that the input contains all possible subsets of size $p$. Our objective is to find a subcollection of minimum cardinality which covers all the elements. This problem is known to be NP-hard. We provide two approximation algorithms for it, one for the generic case, and an improved one for the special case of $(p,k)=(2,4)$. The algorithm for the generic case is a greedy one, based on packing phases: at each phase we pick a collection of disjoint subsets covering $i$ new elements, starting from $i=k$ down to $i=p+1$. At a final step we cover the remaining base elements by the subsets of size $p$. We derive the exact performance guarantee of this algorithm for all values of $k$ and $p$, which is less than $H_k$, where $H_k$ is the $k$th harmonic number. However, the algorithm exhibits the known improvement methods over the greedy one for the unweighted $k$-set cover problem (in which subset sizes are only restricted not to exceed $k$), and hence it serves as a benchmark for our improved algorithm. The improved algorithm for the special case of $(p,k)=(2,4)$ is based on non-oblivious local search: it starts with a feasible cover, and then repeatedly tries to replace sets of size 3 and 4 so as to maximize an objective function which prefers big sets over small ones. For this case, our generic algorithm achieves an asymptotic approximation ratio of $1.5+\varepsilon$, and the local search algorithm achieves a better ratio, which is bounded by $1.458333\cdots +\varepsilon$.},
    identifier   = {05865589},
}