Neil Olver: On the Integrality Gap of the Prize Collecting Steiner Forest LP

Explore a lecture on the integrality gap of the prize collecting Steiner forest LP, delivered as part of the Hausdorff Trimester Program's follow-up workshop on Combinatorial Optimization. Delve into the prize collecting Steiner forest problem, where the objective is to select a subgraph minimizing the sum of edge costs and penalties for unconnected terminal pairs. Discover how the speaker challenges the long-held belief that the integrality gap of the natural LP formulation for this problem is 2, presenting evidence of a gap of at least 9/4, even for planar graphs. Examine the Steiner forest problem, natural cut LP for PCSF, approximation results, and the approximate integer decomposition property. Investigate a potential generalization and an optimistic conjecture before analyzing the construction and integrality gap findings. Gain insights from this collaborative work involving researchers from various institutions, offering a comprehensive exploration of this combinatorial optimization challenge.

Intro
The Steiner forest problem
Natural cut LP for PCSF
Approximation results
The approximate integer decomposition property
A generalization? Optimistic conjecture
The construction
Integrality gap
Conclusion