×

Strong Steiner tree approximations in practice. (English) Zbl 1521.68252


MSC:

68W25 Approximation algorithms
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Y. P. Aneja. 1980. An integer linear programming approach to the Steiner problem in graphs. Networks 10, 2 (1980), 167-178. · Zbl 0445.90087
[2] M. A. Bender and M. Farach-Colton. 2000. The LCA problem revisited. In Proceedings of the Latin American Theoretical Informatics Symposium (LATIN’00) (LNCS), Vol. 1776. 88-94. · Zbl 0959.68133
[3] P. Berman and V. Ramaiyer. 1994. Improved approximations for the Steiner tree problem. J. Algor. 17, 3 (1994), 381-408. · Zbl 0820.68049
[4] M. Bern and P. Plassmann. 1989. The Steiner problem with edge lengths 1 and 2. Inform. Process. Lett. 32, 4 (1989), 171-176. · Zbl 0677.68074
[5] S. Beyer and M. Chimani. 2014. Steiner tree 1.39-approximation in practice. In Proceedings of the Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS’14) (LNCS), Vol. 8934. 60-72.
[6] S. Beyer and M. Chimani. 2015. The influence of preprocessing on Steiner tree approximations. In Proceedings of the International Conference on Combinatorial Optimization and Applications (COCOA’15) (LNCS), Vol. 9486. 601-616. · Zbl 1473.68117
[7] A. Borchers and D.-Z. Du. 1995. The k-Steiner ratio in graphs. In Proceedings of the ACM Symposium on Theory of Computing (STOC’95) (ACM). 641-649. · Zbl 0978.68558
[8] J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità. 2013. Steiner tree approximation via iterative randomized rounding. J. ACM 60, 1 (2013), 6:1-33. · Zbl 1281.68234
[9] D. Chakrabarty, J. Könemann, and D. Pritchard. 2010a. Hypergraphic LP relaxations for Steiner trees. In Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO’10) (LNCS), Vol. 6080. 383-396. · Zbl 1285.90046
[10] D. Chakrabarty, J. Könemann, and D. Pritchard. 2010b. Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound. Operat. Res. Lett. 38, 6 (2010), 567-570. · Zbl 1227.05203
[11] M. Chimani, P. Mutzel, and B. Zey. 2012. Improved Steiner tree algorithms for bounded treewidth. J. Discrete Algor. 16 (2012), 67-78. · Zbl 1257.05166
[12] M. Chimani and M. Woste. 2011. Contraction-based Steiner tree approximations in practice. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC’11) (LNCS), Vol. 7074. 40-49. · Zbl 1329.68286
[13] M. Chlebík and J. Chlebíková. 2008. The Steiner tree problem on graphs: Inapproximability results. Theoret. Comput. Sci. 406, 3 (2008), 207-214. · Zbl 1160.68023
[14] K. Ciebiera, P. Godlewski, P. Sankowski, and P. Wygocki. 2014. Approximation algorithms for Steiner tree problems based on universal solution frameworks. In Proceedings of the 11th DIMACS Challenge. Retrieved from http://arxiv.org/abs/1410.7534.
[15] E. W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numer. Math. 1 (1959), 269-271. · Zbl 0092.16002
[16] DIMACS. 2014. 11th DIMACS Challenge. http://dimacs11.zib.de.
[17] S. E. Dreyfus and R. A. Wagner. 1972. The Steiner problem in graphs. Networks 1 (1972), 195-207. · Zbl 0229.05125
[18] C. W. Duin. 1994. Steiner’s Problem in Graphs: Approximation, Reduction, Variation. Ph.D. Dissertation. Universiteit van Amsterdam.
[19] C. W. Duin and A. Volgenant. 1989. Reduction tests for the Steiner problem in graphs. Networks 19, 5 (1989), 549-567. · Zbl 0673.05088
[20] R. E. Erickson, C. L. Monma, and A. F. Veinott Jr. 1987. Send-and-split method for minimum-concave-cost network flows. Math. Operat. Res. 12, 4 (1987), 634-664. · Zbl 0667.90036
[21] S. Fafianie, H. L. Bodlaender, and J. Nederlof. 2013. Speeding up dynamic programming with representative sets—An experimental evaluation of algorithms for Steiner tree on tree decompositions. In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC’13) (LNCS), Vol. 8246. 321-334. · Zbl 1309.68209
[22] M. Fischetti, M. Leitner, I. Ljubic, M. Luipersbeck, M. Monaci, M. Resch, D. Salvagnin, and M. Sinnl. 2017. Thinning out Steiner trees: A node-based model for uniform edge costs. Math. Program. Comput. 9, 2 (2017), 203-229. · Zbl 1387.90132
[23] R. W Floyd. 1962. Algorithm 97: Shortest path. Commun. ACM 5, 6 (1962), 345.
[24] E. N. Gilbert and H. O. Pollak. 1968. Steiner minimal trees. SIAM J. Appl. Math. 16 (1968), 1-20. · Zbl 0159.22001
[25] M. X. Goemans, N. Olver, T. Rothvoß, and R. Zenklusen. 2012. Matroids and integrality gaps for hypergraphic Steiner tree relaxations. In Proceedings of the ACM Symposium on Theory of Computing (STOC’12). ACM, 1161-1176. · Zbl 1286.05024
[26] M. X. Goemans and D. P. Williamson. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 2 (1995), 296-317. · Zbl 0834.68055
[27] C. Gröpl, S. Hougardy, T. Nierhoff, and H. J. Prömel. 2001. Approximation algorithms for the Steiner tree problem in graphs. In Steiner Trees in Industry (Combinatorial Optimization). 235-279. · Zbl 1042.68635
[28] A. Gubichev and T. Neumann. 2012. Fast approximation of Steiner trees in large graphs. In Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM’12). ACM, 1497-1501.
[29] D. Harel and R. E. Tarjan. 1984. Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13, 2 (1984), 338-355. · Zbl 0535.68022
[30] S. Hougardy and H. J. Prömel. 1999. A 1.598 approximation algorithm for the Steiner problem in graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’99). ACM/SIAM, 448-453. · Zbl 0946.68107
[31] S. Hougardy, J. Silvanus, and J. Vygen. 2017. Dijkstra meets Steiner: A fast exact goal-oriented Steiner tree algorithm. Math. Program. Comput. 9, 2 (2017), 135-202. · Zbl 1387.05252
[32] F. K. Hwang, D. S. Richards, and P. Winter. 1992. The Steiner Tree Problem. Annals of Discrete Mathematics, Vol. 51. Elsevier Science. · Zbl 0774.05001
[33] A. B. Kahng and G. Robins. 1992. A new class of iterative Steiner tree heuristics with good performance. IEEE Trans. CAD Integr. Circ. Syst. 11, 7 (1992), 893-902.
[34] R. M. Karp. 1972. Reducibility among combinatorial problems. In Proceedings of Complexity of Computer Computations 1972 (The IBM Research Symposia Series). 85-103. · Zbl 1467.68065
[35] M. Karpinski and A. Zelikovsky. 1995. 1.757 and 1.267—Approximation algorithms for the network and rectilinear Steiner tree problems. ECCC 2, 3 (1995).
[36] T. Koch and A. Martin. 1998. Solving Steiner tree problems in graphs to optimality. Networks 32, 3 (1998), 207-232. · Zbl 1002.90078
[37] T. Koch, A. Martin, and S. Voß. 2000. SteinLib: An Updated Library on Steiner Tree Problems in Graphs. Technical Report ZIB-Report 00-37. Konrad-Zuse-Zentrum für Informationstechnik Berlin. Retrieved from http://elib.zib.de/steinlib.
[38] J. Könemann, D. Pritchard, and K. Tan. 2011. A partition-based relaxation for Steiner trees. Math. Program. 127, 2 (2011), 345-370. · Zbl 1222.68413
[39] L. T. Kou, G. Markowsky, and L. Berman. 1981. A fast algorithm for Steiner trees. Acta Informatica 15 (1981), 141-145. · Zbl 0445.68051
[40] M. Leitner, I. Ljubic, M. Luipersbeck, and M. Resch. 2014. A partition-based heuristic for the Steiner tree problem in large graphs. In Proceedings of Hybrid Metaheuristics 2014 (LNCS), Vol. 8457. 56-70.
[41] K. Mehlhorn. 1988. A faster approximation algorithm for the Steiner problem in graphs. Inform. Process. Lett. 27, 3 (1988), 125-128. · Zbl 0635.68071
[42] T. Pajor, E. Uchoa, and R. F. Werneck. 2018. A robust and scalable algorithm for the Steiner problem in graphs. Math. Program. Comput. 10, 1 (2018), 69-118. · Zbl 1390.05227
[43] C. H. Papadimitriou and M. Yannakakis. 1988. Optimization, approximation, and complexity classes. In Proceedings of the ACM Symposium on Theory of Computing (STOC’88) (ACM). 229-234.
[44] M. Poggi de Aragão, C. C. Ribeiro, E. Uchoa, and R. F. Werneck. 2001. Hybrid local search for the Steiner problem in graphs. In Proceedings of the Metaheuristics International Conference (MIC’01). 429-433.
[45] M. Poggi de Aragão and R. F. Werneck. 2002. On the implementation of MST-based heuristics for the Steiner problem in graphs. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX’02) (LNCS), Vol. 2409. 1-15. · Zbl 1014.68771
[46] T. Polzin. 2003. Algorithms for the Steiner problem in networks. Ph.D. Dissertation. Universität des Saarlandes.
[47] T. Polzin and S. Vahdati Daneshmand. 2001. Improved algorithms for the Steiner problem in networks. Discrete Appl. Math. 112, 1-3 (2001), 263-300. · Zbl 0994.90135
[48] T. Polzin and S. Vahdati Daneshmand. 2002. Extending reduction techniques for the Steiner tree problem. In Proceedings of the European Symposium on Algorithms (ESA’02) (LNCS), Vol. 2461. 795-807. · Zbl 1019.68613
[49] T. Polzin and S. Vahdati Daneshmand. 2003. On Steiner trees and minimum spanning trees in hypergraphs. Operat. Res. Lett. 31, 1 (2003), 12-20. · Zbl 1013.90131
[50] H. J. Prömel and A. Steger. 1997. RNC-approximation algorithms for the Steiner problem. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS’97) (LNCS), Vol. 1200. 559-570. · Zbl 1498.68213
[51] V. J. Rayward-Smith. 1983. The computation of nearly minimal Steiner trees in graphs. Int. J. Math. Edu. Sci. Technol. 14, 1 (1983), 15-23. · Zbl 0512.05024
[52] G. Robins and A. Zelikovsky. 2005. Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19, 1 (2005), 122-134. · Zbl 1082.05088
[53] M. L. Shore, Leslie R. Foulds, and P. B. Gibbons. 1982. An algorithm for the Steiner problem in graphs. Networks 12, 3 (1982), 323-333. · Zbl 0514.05036
[54] H. Takahashi and A. Matsuyama. 1980. An approximate solution for the Steiner problem in graphs. Math. Japon. 24 (1980), 573-577. · Zbl 0435.05036
[55] S. Vahdati Daneshmand. 2003. Algorithmic Approaches to the Steiner Problem in Networks Ph.D. Dissertation. Universität Mannheim. · Zbl 1013.90131
[56] J. Vygen. 2011. Faster algorithm for optimum Steiner trees. Inform. Process. Lett. 111 (2011), 1075-1079. · Zbl 1260.68305
[57] D. M. Warme. 1998. Spanning Trees in Hypergraphs with Application to Steiner Trees. Ph.D. Dissertation. University of Virginia. · Zbl 0903.90175
[58] R. Wong. 1984. A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28, 3 (1984), 271-287. · Zbl 0532.90092
[59] A. Zelikovsky. 1992. An 11/6-approximation algorithm for the Steiner problem on graphs. Ann. Discrete Math. 51 (1992), 351-354. · Zbl 0768.68193
[60] A. Zelikovsky. 1993a. A faster approximation algorithm for the Steiner tree problem in graphs. Inform. Process. Lett. 46, 2 (1993), 79-83. · Zbl 0770.68078
[61] A. Zelikovsky. 1993b. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 5 (1993), 463-470. · Zbl 0768.68192
[62] A. Zelikovsky. 1995. Better Approximation Bounds for the Network and Euclidean Steiner Tree Problems. Technical Report CS-96-06. University of Virginia.
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.