On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs

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 (3)

• 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

Cited by in corpus (6)

• Spin glass approach to the feedback vertex set problem
• 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