Matroids and integrality gaps for hypergraphic steiner tree relaxations
Original manuscript December 13, 2011
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
2013
|
| Online Access: | http://hdl.handle.net/1721.1/80862 https://orcid.org/0000-0002-0520-1165 |
| _version_ | 1826215494580961280 |
|---|---|
| author | Goemans, Michel X. Olver, Neil Rothvoss, Thomas Zenklusen, Rico |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. Olver, Neil Rothvoss, Thomas Zenklusen, Rico |
| author_sort | Goemans, Michel X. |
| collection | MIT |
| description | Original manuscript December 13, 2011 |
| first_indexed | 2024-09-23T16:31:51Z |
| format | Article |
| id | mit-1721.1/80862 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:31:51Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | mit-1721.1/808622022-10-02T08:13:04Z Matroids and integrality gaps for hypergraphic steiner tree relaxations Goemans, Michel X. Olver, Neil Rothvoss, Thomas Zenklusen, Rico Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. Olver, Neil Rothvoss, Thomas Zenklusen, Rico Original manuscript December 13, 2011 Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to have an integrality gap bounded away from 2, before Byrka et al. [3] showed an upper bound of ~1.55 of a hypergraphic LP relaxation and presented a ln(4)+ε ~1.39 approximation based on this relaxation. Interestingly, even though their approach is LP based, they do not compare the solution produced against the LP value. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem---one that heavily exploits methods and results from the theory of matroids and submodular functions---which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, along the lines of the algorithm of Byrka et al.[3], we present a deterministic ln(4)+ε approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap of hypergraphic relaxations. Similarly to [3], we iteratively fix one component and update the LP solution. However, whereas in [3] the LP is solved at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This potential function gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 ~1.217 upper bound on the integrality gap of hypergraphic relaxations for quasi-bipartite graphs. Additionally, for the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut relaxation to an optimal solution of the hypergraphic relaxation, leading to a fast 73/60 approximation for quasi-bipartite graphs. Furthermore, we show how the separation problem of the hypergraphic relaxation can be solved by computing maximum flows, which provides a way to obtain a fast independence oracle for the matroids that we use in our approach. National Science Foundation (U.S.) (Grant CCF-1115849) National Science Foundation (U.S.) (Grant CCF-0829878) United States. Office of Naval Research (Grant N00014-11-1-0053) United States. Office of Naval Research (Grant N00014-09-1-0326) 2013-09-23T15:34:50Z 2013-09-23T15:34:50Z 2012-05 Article http://purl.org/eprint/type/JournalArticle 9781450312455 http://hdl.handle.net/1721.1/80862 Goemans, Michel X., Neil Olver, Thomas Rothvoss, and Rico Zenklusen. “Matroids and integrality gaps for hypergraphic steiner tree relaxations.” In Proceedings of the 44th symposium on Theory of Computing - STOC 12, 1161. Association for Computing Machinery, 2012. https://orcid.org/0000-0002-0520-1165 en_US http://dx.doi.org/10.1145/2213977.2214081 Proceedings of the 44th symposium on Theory of Computing (STOC '12) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf arXiv |
| spellingShingle | Goemans, Michel X. Olver, Neil Rothvoss, Thomas Zenklusen, Rico Matroids and integrality gaps for hypergraphic steiner tree relaxations |
| title | Matroids and integrality gaps for hypergraphic steiner tree relaxations |
| title_full | Matroids and integrality gaps for hypergraphic steiner tree relaxations |
| title_fullStr | Matroids and integrality gaps for hypergraphic steiner tree relaxations |
| title_full_unstemmed | Matroids and integrality gaps for hypergraphic steiner tree relaxations |
| title_short | Matroids and integrality gaps for hypergraphic steiner tree relaxations |
| title_sort | matroids and integrality gaps for hypergraphic steiner tree relaxations |
| url | http://hdl.handle.net/1721.1/80862 https://orcid.org/0000-0002-0520-1165 |
| work_keys_str_mv | AT goemansmichelx matroidsandintegralitygapsforhypergraphicsteinertreerelaxations AT olverneil matroidsandintegralitygapsforhypergraphicsteinertreerelaxations AT rothvossthomas matroidsandintegralitygapsforhypergraphicsteinertreerelaxations AT zenklusenrico matroidsandintegralitygapsforhypergraphicsteinertreerelaxations |