Approximating set multi-covers

Johnson and Lovász and Stein proved independently that any hypergraph satisfies τ≤(1+lnΔ)τ∗, where τ is the transversal number, τ∗ is its fractional version, and Δ denotes the maximum degree. We prove τf≤3.153τ∗max{lnΔ,f} for the f-fold transversal number τf. Similarly to Johnson, Lovász 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 τf∕f converges to τ∗. 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.