MSc Defence by William Jack Sprent – University of Copenhagen

MSc Defence by William Jack Sprent

The Prize-Collecting Steiner Tree Problem and Related Problems

 

Abstract

The Prize-Collecting Steiner Tree Problem (PCSTP) in graphs is an NP-hard optimisation problem which involves finding a connected subgraph which minimises the total edge cost of the subgraph summed with all vertex prizes not spanned by the subgraph. Multiple exact algorithms, approximation algorithms, and heuristics have been defined for PCSTP, making it a well researched problem.

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 problems, and take a new look at the younger and much less researched problem, the Median Tree Problem (MTP). This problem is a generalisation of the PCSTP where instead of paying static vertex prizes for unspanned vertices, a cost is now paid to \textit{assign} unspanned vertices to the result subgraph.

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