arXiv Analytics

Sign in

arXiv:1704.08680 [cs.DS]AbstractReferencesReviewsResources

Combinatorial 6/5-Approximation of Steiner Tree

Ali Çivril

Published 2017-04-27Version 1

We show that the integrality gap of the bidirected cut relaxation for the Steiner tree problem is at most 6/5 via a primal-dual schema based algorithm.

Comments: 20 pages, 9 figures
Categories: cs.DS
Related articles: Most relevant | Search more
arXiv:1111.6698 [cs.DS] (Published 2011-11-29, updated 2011-12-03)
On the Integrality Gap of the Directed-Component Relaxation for Steiner Tree
arXiv:1107.1630 [cs.DS] (Published 2011-07-08, updated 2014-02-25)
On the Integrality Gap of the Subtour LP for the 1,2-TSP
arXiv:2202.11885 [cs.DS] (Published 2022-02-24)
A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs

Links

Toolbox