Thesis Topics
There are several possible Master-Thesis topics related to the topics discussed in the seminar.
The list might be extended over time.
1. Airports and Railways with Submodular City-Costs
In the airports and railways problem, we want to build airports in some cities and we want to ensure that all cities are connected to airports. We have to pay for building the airports (with costs depending on the cities) and we have to pay for building the connections.
As a graph problem, we are given a complete graph with edge weights and vertex weights. We aim to select a set of vertices A and a set of edges F such that F is a spanning forest and each tree in F contains a vertex from A.
The aim is to minimize the overall cost of A and F.
Open problems: What if the cost functions are submodular?
(Building many airports can decrease the cost per airport; building a large railway network can reduce the cost per km.)
2. Reoptimization of Steiner Forests
In reoptimization, we are given an optimal or very good solution to an instance of an NP-hard problem and a small change of the instance. How good can we solve the changed instance?
This problem is well-studied for Steiner trees. It is completely open for Steiner Forests.