A heuristic algorithm for the prize collecting Steiner Tree problem

The Prize Collecting Steiner Tree (PCST) problem is one of the most important problems in the field of combinatorial optimization. In this paper, we consider new heuristics for the PCST problem. The heuristics consists of two stages. The first stage of the heuristics is to compute a spanning tree, which is based on the greedy approach. In the second stage of the heuristics, each arc in the spanning tree is checked. Throughout this checking, if the deletion of arcs improves the objective function value, then such arcs are deleted from the spanning tree. Next, we implement the heuristics for computational experimentation. In computational experimentation, we use approximation ratio as a key to evaluation values. From our computational experimentation, we confirm that the heuristics method is very fast.