A Fast Vertex-Swap Operator for the Prize-Collecting Steiner Tree Problem

摘要

The prize-collecting Steiner tree problem (PCSTP) is one of the important topics in computational science and operations research. The vertex-swap operation, which involves removal and addition of a pair of vertices based on a given minimum spanning tree (MST), has been proven very effective for some particular PCSTP instances with uniform edge costs. This paper extends the vertex-swap operator to make it applicable for solving more general PCSTP instances with varied edge costs. Furthermore, we adopt multiple dynamic data structures, which guarantee that the total time complexity for evaluating all the O(n~2) possible vertex-swap moves is bounded by O(n) · O(m·log n), where n and m denote the number of vertices and edges respectively (if we run Kruskal's algorithm with a Fibonacci heap from scratch after swapping any pair of vertices, the total time complexity would reach O(n~2) O(m + n·log n)). We also prove that after applying the vertex-swap operation, the resulting solutions are necessarily MSTs (unless infeasible).