Approximation algorithms for Steiner forest: an experimental study. (English) Zbl 1528.90267
Summary: In the Steiner forest problem, we are given a set of terminal pairs and need to find the minimum cost subgraph that connects each of the terminal pairs together. Motivated by the recent work on greedy approximation algorithms for the Steiner forest, we provide efficient implementations of existing approximation algorithms and conduct a thorough experimental study to characterize their performance. We consider several approximation algorithms: the influential primal-dual 2-approximation algorithm due to Agrawal, Klein, and Ravi, the greedy algorithm due to Gupta and Kumar, and a randomized algorithm based on probabilistic approximation by tree metrics. We also consider the simplest heuristic greedy algorithm for the problem, which picks the closest unconnected pair of terminals and connects it using the shortest path between the terminals in the current graph. To characterize the performance of the algorithms, we created a new library with more than one thousand Steiner forest problem instances and conducted an extensive experimental analysis on those instances. Our analysis reveals that for the majority of instances the primal-dual algorithm is the fastest among all the algorithms considered here, and obtains solutions that are very close to the optimal solutions obtained by solving the integer program formulation of the problem.
{© 2021 Wiley Periodicals LLC.}
{© 2021 Wiley Periodicals LLC.}
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C22 | Signed and weighted graphs |
| 90-10 | Mathematical modeling or simulation for problems pertaining to operations research and mathematical programming |
| 90C10 | Integer programming |
References:
| [1] | A.Agrawal, P. N.Klein, and R.Ravi, When trees collide: An approximation algorithm for the generalized Steiner problem on networks, SIAM J Comput24 (1995), 440-456. · Zbl 0831.68071 |
| [2] | Y.Aneja, An integer linear programming approach to the Steiner problem in graphs, Networks10 (1980), 167-178. · Zbl 0445.90087 |
| [3] | B.Awerbuch and Y.Azar, Buy‐at‐bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, Florida, USA, 1997, pp. 542-547. |
| [4] | M.Bateni, M.Hajiaghayi, and D.Marx, Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth, J. ACM58(5) (2011), 21:1-21:37. · Zbl 1281.68233 |
| [5] | J.Beasley, An algorithm for the Steiner problem in graphs, Networks14 (1984), 147-159. · Zbl 0541.90034 |
| [6] | M.Bern and P.Plassmann, The Steiner problem with edge lengths 1 and 2, Inf. Process. Lett.32(4) (1989), 171-176. · Zbl 0677.68074 |
| [7] | S.Beyer and M.Chimani, Strong Steiner tree approximations in practice, ACM J. Exp. Algorithmics24(1) (2019), 1.7:1-1.7:33. · Zbl 1521.68252 |
| [8] | H.‐L.Chen, T.Roughgarden, and G.Valiant, Designing network protocols for good equilibria, SIAM J. Comput.39(5) (2010), 1799-1832. · Zbl 1207.68164 |
| [9] | M.Chlebik and J.Chlebikova, The Steiner tree problem on graphs: Inapproximability results, Theor. Comput. Sci.406(3) (2008), 207-214. · Zbl 1160.68023 |
| [10] | S.Chopra, E.Gorres, and M.Rao, Solving the Steiner tree problem on a graph using branch and cut, ORSA J. Comput.4 (1992), 320-335. · Zbl 0759.90091 |
| [11] | A.Çivril, Approximation of Steiner forest via the bidirected cut relaxation, J. Comb. Optim.38(4) (2019), 1196-1212. · Zbl 1433.90176 |
| [12] | M. P.deAragão and R. F.Werneck, On the implementation of MST‐based heuristics for the Steiner problem in graphs, in Algorithm Engineering and Experiments (ALENEX), D. M.Mount (ed.) and C.Stein (ed.), Eds., Springer, Berlin/Heidelberg, Germany, 2002, 1-15. · Zbl 1014.68771 |
| [13] | C.Duin, Steiner problems in graphs. Ph.D. Thesis, Univ. Amsterdam, 1993. |
| [14] | P.Erdős and A.Rényi, On random graphs I, Publ. Math.6(3) (1959), 290-297. · Zbl 0092.15705 |
| [15] | J.Fakcharoenphol, S.Rao, and K.Talwar, A tight bound on approximating arbitrary metrics by tree metrics, J. Comput. Syst. Sci.69(3) (2004), 485-497. · Zbl 1071.68082 |
| [16] | L.Ghalami, SFlib: A library of approximation algorithms for Steiner forest, 2020, available at https://github.com/lalehghalami/A‐Library‐of‐Approximation‐Algorithms‐f |
| [17] | M. X.Goemans and D. P.Williamson, A general approximation technique for constrained forest problems, SIAM J. Comput.24(2) (1995), 296-317. · Zbl 0834.68055 |
| [18] | M.Groß, A.Gupta, A.Kumar, J.Matuschke, D. R.Schmidt, M.Schmidt, and J.Verschae, A local‐search algorithm for Steiner forest, in Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), A. R.Karlin (ed.), Ed., Schloss Dagstuhl-Leibniz‐Zentrum fuer Informatik, Dagstuhl, Germany, 2018, 31:1-31:17. · Zbl 1462.68140 |
| [19] | A.Gupta and A.Kumar, Greedy algorithms for Steiner forest, Proceedings of the 47th Annual ACM Symposium on Theory of Computing, Portland, OR, USA 2015, pp. 871-878. · Zbl 1321.68504 |
| [20] | M.Hanan, On Steiner’s problem with rectilinear distance, J. SIAM Appl. Math.14(2) (1966), 255-265. · Zbl 0151.33205 |
| [21] | IBMIBM ILOG CPLEX optimization studio for academics initiative, 2018, available at https://ibm.onthehub.com/WebStore/ProductSearchOfferingList.aspx?srch=i |
| [22] | K.Jain, A factor 2 approximation algorithm for the generalized Steiner network problem, Proceedings 39th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA 1998, pp. 448-457. |
| [23] | D.Juhl, D. M.Warme, P.Winter, and M.Zachariasen, The GeoSteiner software package for computing Steiner trees in the plane: An updated computational study, Math. Program. Comput.10 (2018), 487-532. · Zbl 1411.90225 |
| [24] | M.Jünger, A.Martin, G.Reinelt, and R.Weismantel, Quadratic 0/1 optimization and a decomposition approach for the placement of electronic circuits, Math. Program.63 (1994), 257-279. · Zbl 0801.90079 |
| [25] | R. M.Karp, Reducibility among combinatorial problems, in Complexity of computer computations, R.Miller (ed.) and J.Thatcher (ed.), Eds., Plenum Press, New York, NY, 1972, 85-104. · Zbl 1467.68065 |
| [26] | T.Koch, A.Martin, and S.Voß, SteinLib: An updated library on Steiner tree problems in graphs. Technical report ZIB‐Report 00‐37, Vol 7, Konrad‐Zuse‐Zentrum für Informationstechnik Berlin, Takustr, Berlin, Germany, 2000. |
| [27] | J.Könemann, S.Leonardi, G.Schäfer, and S.vanZwam, A group‐strategyproof cost sharing mechanism for the Steiner forest game, SIAM J. Comput.37(5) (2008), 1319-1341. · Zbl 1225.68272 |
| [28] | G.Konjevod, R.Ravi, and F.Salman, On approximating planar metrics by tree metrics, Inf. Process. Lett.80(4) (2001), 213-219. · Zbl 1051.68141 |
| [29] | M.Leitner, I.Ljubic, M.Luipersbeck, M.Prossegger, and M.Resch, New real‐world instances for the Steiner tree problem in graphs. Technical report, ISOR Technical Report, Uni Wien, Wien, 2014. |
| [30] | T. L.Magnanti and S.Raghavan, Strong formulations for network design problems with connectivity requirements, Networks45(2) (2005), 61-79. · Zbl 1067.68104 |
| [31] | PACEPACE: The parameterized algorithms and computational experiments challenge, 2018, available at https://pacechallenge.wordpress.com/pace‐2018/. |
| [32] | T.Polzin and S. V.Daneshmand, Improved algorithms for the Steiner problem in networks, Discret. Appl. Math.112(1) (2001), 263-300. · Zbl 0994.90135 |
| [33] | D.Rehfeldt, A generic approach to solving the Steiner tree problem and variants, Master’s thesis, Technische Universitat Berlin, 2015. |
| [34] | A.Sadeghi and H.Frohlich, Steiner tree methods for optimal sub‐network identification: An empirical study, BMC Bioinform14 (2013), 144. |
| [35] | D. R.Schmidt, B.Zey, and F.Margot, MIP formulations for the Steiner forest problem, CoRR (2017), abs/1709.01124. |
| [36] | SteinForestLibA collection of Steiner forest problems in graphs, 2020, available at https://github.com/lalehghalami/SteinForestProblem. |
| [37] | SteinLibA collection of Steiner tree problems in graphs and variants, 2015, available at http://steinlib.zib.de/steinlib.php. |
| [38] | S.Tazari and M.Müller‐Hannemann, Dealing with large hidden constants: Engineering a planar Steiner tree PTAS, ACM J. Exp. Algorithmics16 (2011). · Zbl 1284.05311 |
| [39] | E.Uchoa and R. F.Werneck, Fast local search for Steiner trees in graphs, Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX), Austin, Texas, USA, 2010, pp. 1‐10. · Zbl 1430.68248 |
| [40] | V. V.Vazirani, Approximation algorithms, Springer‐Verlag, Berlin/Heidelberg, Germany, 2001. · Zbl 1138.90417 |
| [41] | D.Warme, P.Winter, and M.Zachariasen, GeoSteiner: Software for computing Steiner trees, 2018, available at http://www3.cs.stonybrook.edu/∼algorith/implement/geosteiner/implement · Zbl 1411.90225 |
| [42] | D. P.Williamson and D. B.Shmoys, The design of approximation algorithms, Cambridge University Press, Cambridge, MA, 2011. · Zbl 1219.90004 |
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.
