Approximating set multi-covers

Johnson and Lov'asz and Stein proved independently that any hypergraph satisfies $\tau \le (1+\ln \mathrm{\Delta }){\tau }^{\ast }$, where $\tau$ is the transversal number, ${\tau }^{\ast }$ is its fractional version, and $\mathrm{\Delta }$ denotes the maximum degree. We prove ${\tau }_f\le c{\tau }^{\ast }\max \{\ln \mathrm{\Delta },f\}$ for the $f$-fold transversal number ${\tau }_f$. Similarly to Johnson, Lov'asz and Stein, we also show that this bound can be achieved non-probabilistically, using a greedy algorithm. As a combinatorial application, we prove an estimate on how fast ${\tau }_f\mathrm{/}f$ converges to ${\tau }^{\ast }$. As a geometric application, we obtain an upper bound on the minimal density of an $f$-fold covering of the $d$-dimensional Euclidean space by translates of any convex body.