  In the Set Cover problem, we are given a set system with each set having a
weight, and we want to find a collection of sets that cover the universe,
whilst having low total weight. There are several approaches known (based on
greedy approaches, relax-and-round, and dual-fitting) that achieve a $H_k
\approx \ln k + O(1)$ approximation for this problem, where the size of each
set is bounded by $k$. Moreover, getting a $\ln k - O(\ln \ln k)$ approximation
is hard.
  Where does the truth lie? Can we close the gap between the upper and lower
bounds? An improvement would be particularly interesting for small values of
$k$, which are often used in reductions between Set Cover and other
combinatorial optimization problems.
  We consider a non-oblivious local-search approach: to the best of our
knowledge this gives the first $H_k$-approximation for Set Cover using an
approach based on local-search. Our proof fits in one page, and gives a
integrality gap result as well. Refining our approach by considering larger
moves and an optimized potential function gives an $(H_k - \Omega(\log^2
k)/k)$-approximation, improving on the previous bound of $(H_k -
\Omega(1/k^8))$ (\emph{R.\ Hassin and A.\ Levin, SICOMP '05}) based on a
modified greedy algorithm.
