MSc Defence by William Jack Sprent
The Prize-Collecting Steiner Tree Problem and Related Problems
The Prize-Collecting Steiner Tree Problem (PCSTP) in graphs is an NP-hard
In this master's thesis, we present a comprehensive survey of the research landscape on the PCSTP. This involves a thorough look at some of the most interesting and important algorithms for the PCSTP. Among the surveyed subjects are powerful preprocessing routines, the widely cited Goemans-Williamson approximation algorithm, and two state-of-the-art solvers.
We make use of this survey to consider the relation of the PCSTP and other close
For the MTP we present a new integer linear programming formulation as well as a solver which is able to generate exact solutions to the problem. Furthermore, we present a new dataset based on previously released datasets for the PCSTP.
Supervisor: Pawel Winter
External Examiner: Jesper Larsen, DTU