Approximating set multi-covers

Abstract

Johnson and Lovász and Stein proved independently that any hypergraph satisfies $\tau \le (1+\ln \Delta ){\tau }^{\ast }$, where $\tau$ is the transversal number, ${\tau }^{\ast }$ is its fractional version, and $\Delta$ denotes the maximum degree. We prove ${\tau }_f\le c{\tau }^{\ast }\max \{\ln \Delta ,f\}$ for the $f$-fold transversal number ${\tau }_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 ${\tau }_f/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.

THE TITLE CHANGED! This is the final version. 7 pages

References in corpus (1)

• Coverings: variations on a result of Rogers and on the Epsilon-net theorem of Haussler and Welzl

Cited by in corpus (1)

• Covering compact metric spaces greedily