
A Sharp Bound on the Integrality Gap in the 3-Set Cover Problem
Eli Berger of the University of Haifa presents a result in combinatorial optimization, delivered as part of the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar. The talk addresses 3-set cover, where edges of size at most three must cover a hypergraph's vertex set, a problem known to be NP-hard. Berger works through the integrality gap, the ratio between the true optimum and its linear programming relaxation, tracing prior bounds from Lovasz's classic 11/6 result down to Fujito and Okumura's 5/3, before proving a sharp bound of 3/2. He shows this is best possible and walks through two consequences: a covering guarantee for regular 3-uniform hypergraphs that resolves the k=3 case of a problem posed by de A. Moreira and Kohayakawa, and a triples version of the Gale-Shapley stable marriage theorem. The proof techniques and their applications are laid out step by step on the board for an audience of specialists.