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 & 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?