On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
arXiv:1309.0346 · doi: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 Linear/Integer 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 post-processing procedures defined in the Goemans-Williamson derivative and global optimality in some limit cases.
References in corpus (5)
- Learning by message-passing in networks of discrete synapses
- Finding undetected protein associations in cell signaling by belief propagation
- Statistical Mechanics of Steiner trees
- A rigorous analysis of the cavity equations for the minimum spanning tree
- A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
Cited by in corpus (7)
- Spin glass approach to the feedback vertex set problem
- Optimizing spread dynamics on graphs by message passing
- Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
- Solving the undirected feedback vertex set problem by local search
- The cavity approach for Steiner trees packing problems
- Practical optimization of Steiner Trees via the cavity method
- A cavity approach to optimization and inverse dynamical problems