Bounded-cardinality bounded-frequency set cover: hardness of approximation Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.


Example: the case $k = 4$ and $f = 2$ is equivalent to the minimum vertex cover problem in graphs with maximum degree 4.


Let $a(k,f) > 1$ be the largest value such that finding an $a(k,f)$-approximation of the minimum set cover problem with parameters $k$ and $f$ is NP-hard.


Example: $a(4,2) \ge 1.0128$ (Berman &amp; Karpinski 1999).


Question: Do we have a reference that summarises the strongest known lower bounds on $a(k,f)$? In particular, I'm interested in concrete values in the case that both $k$ and $f$ are small but $f > 2$.



Restricted versions of the set cover problem are often convenient in reductions; typically there is some freedom in choosing the values of $k$ and $f$, and further information on $a(k,f)$ would help to choose the right values that provide the strongest hardness results. References here, here, and here provide a starting point, but the information is somewhat outdated and fragmentary. I was wondering if there is a more complete and up-to-date source?
Using the more common parameter notation $(\Delta,k)$ instead of $(k,f)$, this is equivalent to (and I think more commonly known as) the Vertex Cover problem in $k$-uniform hypergraphs of maximum degree $\Delta$.  To emphasize, for consistency with the literature I'm using $k$ where you use $f$, and $\Delta$ where you use $k$.

For any constant $\varepsilon > 0$, results ignoring $\Delta$ include


$\sup_\Delta\{ a(\Delta,k) \}\leq k$ from general set cover.
$\sup_\Delta\{ a(\Delta,k) \}\geq k-1-\varepsilon$ (Dinur et al., 2004), as noted by Lev.
If the unique games conjecture is true, then $\sup_\Delta \{a(\Delta,k)\} \geq k-\varepsilon$, which is tight (Khot &amp; Regev, 2008).


Ignoring $k$, 


$\sup_k\{ a(\Delta,k) \}\leq \Delta$ (trivial).
$\sup_k\{ a(4,k) \}\geq 2-\varepsilon$ (Holmerin, 2002)


The only result I know that combines the two parameters is 


$a(\Delta,k) \leq k - (1-o(1))\left(\frac{k(k-1)\ln\ln\Delta}{\ln(\Delta)}\right)$ for fixed $k$, or $k$ growing slowly with $\Delta$ (Halperin, 2002)


There is a connection between this problem and the (Weak) Independent Set problem, but I'm not exactly sure how they're related in terms of approximability.  I would recommend investigating this, perhaps starting here: [PDF].