{"id":"arxiv/2606.16921","url":"https://arxiv.org/abs/2606.16921","tags":["math.CO"],"score":0,"title":"A sharp bound on the integrality gap in the 3-set cover problem","domain":"math.CO","source":"arxiv","authors":["Eli Berger","Ron Holzman"],"reviews":0,"subject":"math.CO","summary":"Given a hypergraph with edges of size at most 3, the 3-set cover problem asks to determine the minimum size of a family of edges which covers the vertex set. As the problem is NP-hard, it is natural to consider its fractional (linear programming) relaxation, which provides a lower bound on the value of the optimal solution. The ratio between the actual value and that of the fractional relaxation is called the integrality gap. A classic bound of Lovász implies that the integrality gap in this problem is at most 11/6. This has been improved to 5/3 by Fujito and Okumura. Here we prove that the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-15","reactions":{}}