A sharp bound on the integrality gap in the 3-set cover problem
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.16921
curl -X POST /api/v1/records/arxiv/2606.16921/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.16921/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'