- Access by Xinjiang University
Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs
Phys. Rev. E 86, 026706 – Published 13 August, 2012
DOI: https://doi.org/10.1103/PhysRevE.86.026706
Abstract
We study the behavior of an algorithm derived from the cavity method for the prize-collecting steiner tree (PCST) problem on graphs. The algorithm is based on the zero temperature limit of the cavity equations and as such is formally simple (a fixed point equation resolved by iteration) and distributed (parallelizable). We provide a detailed comparison with state-of-the-art algorithms on a wide range of existing benchmarks, networks, and random graphs. Specifically, we consider an enhanced derivative of the Goemans-Williamson heuristics and the dhea solver, a branch and cut integer linear programming based approach. The comparison shows that the cavity algorithm outperforms the two algorithms in most large instances both in running time and quality of the solution. Finally we prove a few optimality properties of the solutions provided by our algorithm, including optimality under the two postprocessing procedures defined in the Goemans-Williamson derivative and global optimality in some limit cases.
Article Text
References (23)
- M. Mézard and A. Montanari, Information, Physics and Computation (Oxford University Press, New York, 2009).
- S. S. Huang and E. Fraenkel, Integrating Proteomic, Transcriptional, and Interactome Data Reveals Hidden Components of Signaling and Regulatory Networks, Sci. Signaling 2: ra40 (2009).
- M. Bailly-Bechet, C. Borgs, A. Braunstein, J. Chayes, and A. Dagkessamanskaia, PNAS 108, 882 (2011).
- M. Bailly-Bechet, A. Braunstein, and R. A. Zecchina, in Proceedings of the 7th International Conference on Computational Methods in Systems Biology (Springer, New York, 2009), p. 95.
- J. Hackner, Ph.D. thesis, Vienna University of Technology, Austria, 2004.
- M. X. Goemans and D. P. Williamson, in Approximation Algorithms for NP-Hard Problems, edited by D. S. Hochbaum (PWS, Boston, 1997), pp. 144–191.
- D. Johnson, M. Minkoff, and S. Phillips, in Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia, 2000), pp. 760–769.
- I. Ljubic, R. Weiskircher, U. Pferschy, G. Klau, P. Mutzel, and M. Fischetti, Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments (Society for Industrial and Applied Mathematics, Philadelphia, 2005).
- M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina, Phys. Rev. Lett. 101, 037208 (2008).
- O. Angel, A. D. Flaxman, and D. B. Wilson, Combinatorica 32, 1 (2012).
- D. Aldous, Random Structures and Algorithms 18, 381 (2001).
- A. Lucena and M. G. C. Resende, Discrete Appl. Math. 141, 277 (2004).
- M. Bayati, A. Braunstein, and R. Zecchina, J. Math. Phys. 49, 125206 (2008).
- M. Mézard, G. Parisi, and R. Zecchina, Science 297, 812 (2002).
- A. Braunstein and R. Zecchina, Phys. Rev. Lett. 96, 030201 (2006).
- CMP Group website: www.polito.it/cmp.
- A. Salles da Cunha, A. Lucena, N. Maculan, and M. G. C. Resende, Discrete Applied Mathematics 157, 1198 (2009).
- K. Aardal and S. van Hoesel, Stat Nederlandica 50, 3 (1996).
- G. B. Dantzig and M. N. Thapa, Linear Programming: Theory and Extensions, Vol. 2 (Springer, New York, 2003).
- Ivana Ljubic site: http://homepage.univie.ac.at/ivana.ljubic/research/pcstp/.
- S. A. Canuto, M. G. C. Resende, and C. C. Ribeiro, Networks 38, 50 (2001).
- I. Rosseti, M. Poggi de Arago, C. C. Ribeiro, E. Uchoa, and R. F. Werneck, New Benchmark Instances for the Steiner Problem in Graphs, Extended Abstracts of the 4th Metaheuristics International Conference (2001), pp. 557–561.
- D. Cees and S. Vob, Networks 29, 89 (1997).