Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

Hausdorff Center for Mathematics via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.

Syllabus

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

Taught by

Hausdorff Center for Mathematics

Reviews

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

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.