On the Exact Solution of Prize-Collecting Steiner Tree Problems

References

• Achterberg T (2007) Constraint integer programming. PhD thesis, Technische Universität Berlin, Berlin.Google Scholar
• Akhmedov M, Kwee I, Montemanni R (2016) A divide and conquer matheuristic algorithm for the prize-collecting Steiner Tree Problem. Comput. Oper. Res. 70:18–25.Crossref, Google Scholar
• Álvarez-Miranda E, Ljubić I, Mutzel P (2013) The maximum weight connected subgraph problem. Facets of Combinatorial Optimization (Springer, Berlin), 245–270Crossref, Google Scholar
• Archer A, Bateni M, Hajiaghayi M, Karloff H (2011) Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40(2):309–332.Crossref, Google Scholar
• Bateni M, Chekuri C, Ene A, Hajiaghayi M, Korula N, Marx D(2011) Prize-collecting Steiner problems on planar graphs. Proc. 22nd Annual ACM-SIAM Sympos. on Discrete Algorithms (ACM/SIAM, New York/Philadelphia), 1028–1049.Crossref, Google Scholar
• Biazzo I, Braunstein A, Zecchina R (2012) Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs. Phys. Rev. E 86:026706.Crossref, Google Scholar
• Bienstock D, Goemans MX, Simchi-Levi D, Williamson DP (1993) A note on the prize collecting traveling salesman problem. Math. Programming 59:413–420.Crossref, Google Scholar
• Bolukbasi G, Kocaman AS (2018) A prize collecting Steiner tree approach to least cost evaluation of grid and off-grid electrification systems. Energy 160:536–543.Crossref, Google Scholar
• Braunstein A, Muntoni A (2016) Practical optimization of Steiner trees via the cavity method. J. Statist. Mechanics Theory Experiment 2016(7):073302.Crossref, Google Scholar
• Buchanan A, Wang Y, Butenko S (2018) Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph. Networks 72(2):238–248.Crossref, Google Scholar
• Canuto SA, Resende MGC, Ribeiro CC (2001) Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks 38(1):50–58.Crossref, Google Scholar
• da Cunha AS, Lucena A, Maculan N, Resende MG (2009) A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs. Discrete Appl. Math. 157(6):1198–1217.Crossref, Google Scholar
• Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerical Math. 1(1):269–271.Crossref, Google Scholar
• DIMACS (2015) 11th DIMACS Challenge. Accessed January 10, 2020, http://dimacs11.zib.de/.Google Scholar
• Dittrich M, Klau G, Rosenwald A, Dandekar T, Müller T (2008) Identifying functional modules in protein-protein interaction networks: An integrated exact approach. Bioinformatics 24:i223–i231.Crossref, Google Scholar
• Dreyfus SE, Wagner RA (1971) The Steiner problem in graphs. Networks 1(3):195–207.Crossref, Google Scholar
• Duin C (1993) Steiner problems in graphs. PhD thesis, University of Amsterdam, Amsterdam.Google Scholar
• Feofiloff P, Fernandes CG, Ferreira CE, de Pina JC (2007) Primal-dual approximation algorithms for the prize-collecting Steiner tree problem. Inform. Processing Lett. 103(5):195–202.Crossref, Google Scholar
• Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, Salvagnin D, et al. (2017) Thinning out Steiner trees: A node-based model for uniform edge costs. Math. Programming Comput. 9(2):203–229.Crossref, Google Scholar
• Fu Z, Hao J (2017) Knowledge-guided local search for the prize-collecting Steiner tree problem in graphs. Knowledge-Based Systems 128:78–92.Crossref, Google Scholar
• Gamrath G, Koch T, Maher S, Rehfeldt D, Shinano Y (2017) SCIP-Jack: A solver for STP and variants with parallelization extensions. Math. Programming Comput. 9(2):231–296.Crossref, Google Scholar
• Goemans MX, Myung Y (1993) A catalog of Steiner tree formulations. Networks 23(1):19–28.Crossref, Google Scholar
• Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2):296–317.Crossref, Google Scholar
• Hidayati SC, Hua K, Tsao Y, Shuai H, Liu J, Cheng W (2019) Garment detectives: Discovering clothes and its genre in consumer photos. Proc. 2019 IEEE Conf. on Multimedia Inform. Processing and Retrieval (IEEE, New York), 471–474.Crossref, Google Scholar
• Ideker T, Ozier O, Schwikowski B, Siegel AF (2002) Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics 18(1):S233–S240.Crossref, Google Scholar
• Johnson DS, Minkoff M, Phillips S (2000) The prize collecting Steiner Tree Problem: Theory and practice. Proc. 11th Annual ACM-SIAM Sympos. on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 760–769.Google Scholar
• Karp R (1972) Reducibility among combinatorial problems. Miller R, Thatcher J, eds. Complexity of Computer Computations (Plenum Press), 85–103.Crossref, Google Scholar
• Klau GW, Ljubić I, Moser A, Mutzel P, Neuner P, Pferschy U, Raidl G, et al. (2004) Combining a memetic algorithm with integer programming to solve the prize-collecting Steiner tree problem. Deb K, ed. Genetic and Evolutionary Computation (Springer, Berlin), 1304–1315.Google Scholar
• Klein P, Ravi R (1995) A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19(1):104–115.Crossref, Google Scholar
• Koch T, Martin A (1998) Solving Steiner tree problems in graphs to optimality. Networks 32:207–232.Crossref, Google Scholar
• Leitner M, Ljubic I, Luipersbeck M, Sinnl M (2018) A dual ascent-based branch-and-bound framework for the Prize-Collecting Steiner Tree and related problems. INFORMS J. Comput. 30(2):402–420.Link, Google Scholar
• Ljubic I (2004) Exact and memetic algorithms for two network design problems. PhD thesis, Vienna University of Technology, Vienna.Google Scholar
• Ljubic I, Weiskircher R, Pferschy U, Klau GW, Mutzel P, Fischetti M (2006) An algorithmic framework for the exact solution of the prize-collecting Steiner Tree Problem. Math. Programming 105(2-3):427–449.Crossref, Google Scholar
• Ming YF, Chen SB, Chen YQ, Fu ZH (2018) A fast vertex-swap operator for the prize-collecting Steiner tree problem. Shi Y, Fu H, Tian Y, Krzhizhanovskaya VV, Lees MH, Dongarra J, Sloot PMA, eds. Computational Science (Springer International Publishing, Cham, Switzerland), 553–560.Crossref, Google Scholar
• Polzin T, Daneshmand SV (2001) Improved algorithms for the Steiner Problem in networks. Discrete Appl. Math. 112(1-3):263–300.Crossref, Google Scholar
• Polzin T, Daneshmand SV (2002) Extending Reduction Techniques for the Steiner Tree Problem (Springer, Berlin).Crossref, Google Scholar
• Rehfeldt D, Koch T (2018) Transformations for the Prize-Collecting Steiner Tree Problem and the maximum-weight connected subgraph problem to SAP. J. Comput. Math. 36(3):459–468.Crossref, Google Scholar
• Rehfeldt D, Koch T (2019) Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem. SIAM J. Optim. 29(1):369–398.Crossref, Google Scholar
• Rehfeldt D, Koch T, Maher SJ (2019) Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem. Networks 73(2):206–233.Crossref, Google Scholar
• Rosseti I, de Aragão MP, Ribeiro CC, Uchoa E, Werneck RF (2004) New Benchmark Instances for The Steiner Problem in Graphs (Springer, Boston).Google Scholar
• Savelsbergh MWP (1994) Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6(4):445–454.Link, Google Scholar
• Schmidt L, Hegde C, Indyk P, Lu L, Chi X, Hohl D (2015) Seismic feature extraction using Steiner tree methods. Proc. 015 IEEE Internat. Conf. Acoustics, Speech Signal Processing (IEEE, New York), 1647–1651.Google Scholar
• Sun Y, Brazil M, Thomas D, Halgamuge S (2019) The fast heuristic algorithms and post-processing techniques to design large and low-cost communication networks. IEEE/ACM Trans. Networking 27(1):375–388.Crossref, Google Scholar
• Uchoa E (2006) Reduction tests for the prize-collecting Steiner problem. Oper. Res. Lett. 34(4):437–444.Crossref, Google Scholar
• Wong R (1984) A dual ascent approach for Steiner tree problems on a directed graph. Math. Programming 28:271–287.Crossref, Google Scholar