An Improved Integrality Gap for Steiner Tree

Ali Çivril, Muhammed Mirza Biçer, Berkay Tahsin Tunca +1

A promising approach for obtaining improved approximation algorithms for Steiner tree is to use the bidirected cut relaxation (BCR). The integrality gap of this relaxation is at le…