Abstract
Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an LP whose dual is equivalent to this relaxation. This opens up the possibility of using the primal-dual schema in a geometric setting for designing an algorithm for this problem. Using this approach, we obtain a 4/3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; the previous best integrality gap upper bound being 3/2 (Rajagopalan and Vazirani in On the bidirected cut relaxation for the metric Steiner tree problem, 1999). We also obtain a factor \({\sqrt{2}}\) strongly polynomial algorithm for this class of graphs. A key difficulty experienced by researchers in working with the bidirected cut relaxation was that any reasonable dual growth procedure produces extremely unwieldy dual solutions. A new algorithmic idea helps finesse this difficulty—that of reducing the cost of certain edges and constructing the dual in this altered instance—and this idea can be extracted into a new technique for running the primal-dual schema in the setting of approximation algorithms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agarwal, A., Charikar, M.: On the advantage of network coding for improving network throughput. In: Proceedings of the IEEE Information Theory Workshop (2004)
Calinescu, G., Karloff, H.J., Rabani, Y.: An improved algorithm for the MULTIWAY CUT. Proceedings of Symposium on Theory of Computation (STOC) (1998)
Chekuri C., Gupta A., Kumar A.: On a bidirected relaxation for the MULTIWAY CUT problem. Discret. Appl. Math. 150(1-3), 67–79 (2005)
Chlebik, M., Chlebikova, J.: Approximation hardness of the steiner tree problem on graphs. Proceedings of Scandinavian Workshop on Algorithm Theory (2002)
Cormen T., Leiserson C., Rivest R., Stein C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill, Boston (2001)
Chopra S., Rao M.R.: The Steiner tree problem I: formulations, compositions and extension of facets. Math. Program. 64, 209–229 (1994)
Chopra S., Rao M.R.: The Steiner tree problem II: properties and classes of facets. Math. Program. 64, 231–246 (1994)
Courant, R., Robbins, H., Stewart, I.: What Is Mathematics? An Elementary Approach to Ideas and Methods. Oxford Papebacks (1996)
Edmonds J.: Optimum branchings. J. Res. Natl. Bureau Stand. Sect. B 71, 233–240 (1967)
Goemans M., Myung Y.: A catalog of Steiner tree formulations. Networks 23, 19–23 (1993)
Goemans, M.: Personal communication with third author. (1996)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM. pp. 1115–1145, (1995)
Hwang F.K., Richards D.S., Winter P.: The Steiner Tree Problem, vol. 53 of Annals of Discrete Mathematics. North-Holland, Amsterdam (1992)
Ivanov A.O., Tuzhilin A.A.: The Steiner Problem and its Generalizations. CRC Press, BocaRaton (1994)
Jain, K., Vazirani, V.V.: Equitable cost allocations via primal-dual-type algorithms. In: Proceedings of 33rd ACM Symposium on Theory of Computing (2002)
Karger D., Klein P., Stein C., Thorup M., Young N.: Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res. 29(3), 436–461 (2004)
Könemann, J., Pritchard, D., Tan, K.: A partition based relaxation for Steiner trees. Manuscript (2007)
Rizzi R.: On Rajagopalan and Vazirani’s 3/2-approximation bound for the iterated 1-Steiner heuristic. Inf. Process. Lett. 86, 335–338 (2003)
Rajagopalan, S., Vazirani, V.: On the bidirected cut relaxation for the metric Steiner tree problem. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete algorithms (1999)
Robins G., Zelikovsky A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discret. Math. 19, 122–134 (2005)
Vazirani V.V.: Approximation Algorithms, 2nd edn. Springer, UK (2001)
Wong R.T.: A dual ascent approach for Steiner trees on a directed graph. Math. Program. 28, 271–287 (1984)
Author information
Authors and Affiliations
Corresponding author
Additional information
Work supported by NSF Grant CCF-0728640. Preliminary version of this work appeared in the Thirteenth Conference on Integer Programming and Combinatorial Optimization (IPCO), May 26–28, 2008.
Rights and permissions
About this article
Cite this article
Chakrabarty, D., Devanur, N.R. & Vazirani, V.V. New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Math. Program. 130, 1–32 (2011). https://doi.org/10.1007/s10107-009-0299-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-009-0299-0