On the Integrality Gap of the Prize-Collecting Steiner Forest LP

Jochen Könemann, Neil Olver, Kanstantsin Pashkovich +3

In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph $G=(V,E)$, edge costs $\{c_e\ge 0{\}}_{e\in E}$, terminal pairs $\{(s_i,t_i){\}}_{i=1}^k$, and…