×

Approximation of Steiner forest via the bidirected cut relaxation. (English) Zbl 1433.90176

Summary: The classical algorithm of A. Agrawal et al. [SIAM J. Comput. 24, No. 3, 440–456 (1995; Zbl 0831.68071)], stated in the setting of the primal-dual schema by M. X. Goemans and D. P. Williamson [SIAM J. Comput. 24, No. 2, 296–317 (1995; Zbl 0834.68055)] uses the undirected cut relaxation for the Steiner forest problem. Its approximation ratio is \(2-\frac{1}{k} \), where \(k\) is the number of terminal pairs. A variant of this algorithm more recently proposed by J. Könemann et al. [SIAM J. Comput. 37, No. 5, 1319–1341 (2008; Zbl 1225.68272)] is based on the lifted cut relaxation. In this paper, we continue this line of work and consider the bidirected cut relaxation for the Steiner forest problem, which lends itself to a novel algorithmic idea yielding the same approximation ratio as the classical algorithm. In doing so, we introduce an extension of the primal-dual schema in which we run two different phases to satisfy connectivity requirements in both directions. This reveals more about the combinatorial structure of the problem. In particular, there are examples on which the classical algorithm fails to give a good approximation, but the new algorithm finds a near-optimal solution.

MSC:

90C35 Programming involving graphs or networks
68W25 Approximation algorithms
68Q25 Analysis of algorithms and problem complexity

References:

[1] Agrawal A, Klein PN, Ravi R (1991) When trees collide: an approximation algorithm for the generalized Steiner problem on networks. In: Proceedings of the 23rd annual ACM symposium on theory of computing (STOC), pp 134-144
[2] Agrawal A, Klein PN, Ravi R (1995) When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J Comput 24(3):440-456 · Zbl 0831.68071 · doi:10.1137/S0097539792236237
[3] Chopra S, Rao MR (1994) The Steiner tree problem I: formulations, compositions and extension of facets. Math Program 64:209-229 · Zbl 0821.90124 · doi:10.1007/BF01582573
[4] Goemans MX, Myung Y-S (1993) A catalog of steiner tree formulations. Networks 23(1):19-28 · Zbl 0794.90074 · doi:10.1002/net.3230230104
[5] Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J Comput 24(2):296-317 · Zbl 0834.68055 · doi:10.1137/S0097539793242618
[6] Goemans MX et al (1994) Improved approximation algorithms for network design problems. In: Proceedings of the 5th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 223-232 · Zbl 0873.68005
[7] Groß M, Gupta A, Kumar A, Matuschke J, Schmidt DR, Schmidt M, Verschae J (2018) A local-search algorithm for Steiner forest. In: 9th innovations in theoretical computer science conference, ITCS. pp 31:1-31:17 · Zbl 1462.68140
[8] Gupta A, Kumar A (2015) Greedy algorithms for Steiner forest. In: Proceedings of the 47th annual ACM symposium on theory of computing (STOC), pp 871-878 · Zbl 1321.68504
[9] Könemann J et al (2008) A group-strategyproof cost sharing mechanism for the Steiner forest game. SIAM J Comput 37(5):1319-1341 · Zbl 1225.68272 · doi:10.1137/050646408
[10] Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, Cambridge · Zbl 1219.90004 · doi:10.1017/CBO9780511921735
[11] Williamson DP et al (1995) A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica 15:708-717 · Zbl 0838.90133 · doi:10.1007/BF01299747
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.