Approximating set multi-covers

Márton Naszódi, Alexandr Polyanskii

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…