An Improved Integrality Gap for Steiner Tree

2017/04/27 by Ali Çivril, Muhammed Mirza Biçer, Çivril, Ali +5
#cs.DS

paper · pdf · doi:10.48550/arxiv.1704.08680

Abstract

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 least 36/31, and it has long been conjectured that its true value is very close to this lower bound. However, the best upper bound for general graphs was an almost trivial 2. We improve this bound to 3/2 by a combinatorial algorithm based on the primal-dual schema.

Citations

• Steiner Tree Approximation via Iterative Randomized Rounding

Related

• Simplex based Steiner tree instances yield large integrality gaps for the bidirected cut relaxation
• The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
• Integrality Gap of the Hypergraphic Relaxation of Steiner Trees: a short proof of a 1.55 upper bound
• A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
• Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations