Departmental Bulletin Paper Prize Collecting Steiner Tree 問題に対するヒューリスティクス

細川, 祐樹

The Prize Collecting Steiner Tree (PCST) problem is an important problem in the eldof combinatorial optimization. In this reearch, we develop two heuristics (H1, H2) for PCST problems. The heuristics consists of two stages. In the first stage, a spanning tree is computed, which is based on these heuristics. In the second stage, we delete vertices to improve the objectivefunction value. Through computational experimentations, we found that method H1 is faster than method H2. Given a set of real-world instances, we obtained a good approximation ratio in both methods H1 and H2.Key Words : Prize Collecting Steiner Tree Problem, Heuristic, Benchmark Instance

Number of accesses :  

Other information