My research interests include:
- Algorithm Engineering
- Parameterized Algorithms and Complexity
- Computational Geometry
- Graph Parameters
I am especially interested in intersections between those topics, like parameters for geometric graphs or parameterized algorithms for geometric problems.
Details of some of my current projects can be found below.
DAAD Prime: Geometric Routing Problems in Restricted Settings
Routing problems have many applications, such as logistics, tourism, travel planning, and several more. In general, routing problems simply ask for the best route(s) in a given setting. Algorithms for these problems have been studied extensively in computer science over the last century.
The most famous is the Travelling Salesperson Problem (TSP), which has been studied since the 1930s: Given a set of cities and their pairwise distances, what is the shortest route to visit each city exactly once and return to the starting city? Formally, this can be stated as a graph problem: we are given a (complete,) weighted graph and ask for the minimum weight Hamiltonian cycle, i.e. a cycle that visits each vertex exactly once. Since many applications are inherently geometric, the Euclidean version of the TSP receives a lot of attention: Here we take as input a Euclidean graph, i.e. a graph whose vertices correspond to points in the Euclidean plane and whose edge weights correspond to their Euclidean distances.
While even the Euclidean TSP is NP-hard, efficient algorithms have been studied extensively. First approximation algorithms have been known since the 1970s, and later results gave polynomial-time approximation schemes.
Recently, the Euclidean TSP has received considerable attention in several restricted contexts, such as narrow stripes and simple polygons. However, other routing problems – often generalisations of the TSP – have not been studied as extensively. In this project, we aim to investigate several of these routing problems in constrained settings. Specifically, we will focus on the Orienteering Problem, the Vehicle Routing Problem, and the Team Orienteering Problem. We will study these problems and their variants with time windows, considering $1$-dimensional point sets, bitonic versions, narrow strips, simple polygons, and instances with bounded tree-width.
DFG – Project: (Directed) Graph Parameters for Geometric Spanners
Geometric graphs are of high interest for many applications: Road and train networks, robot motion planning, wireless ad-hoc networks, and many more. To work with and run algorithms on these graphs, it is often useful to approximate the complete graph by smaller versions of the graph, in particular by a graph with fewer edges. However, there are important properties which should not be altered by this. Especially the distance between two points in the graph should not get much larger than their distance in a complete euclidean graph: a graph with this property is called $geometric\ spanner$.
Formally, let $P$ be a point set in the euclidean plane. A geometric spanner for $P$ is a weighted subgraph $G=(P,E,w)$ of the complete graph on $P$, where the weight $w(e)$ of an edge $e$ is the euclidean distance between the start and ending point of $e$. The idea of a geometric spanner is finding an edge set $E$ which is not too big while the path between two points in $P$ does not get too long. This is formalised by the so-called dilation factor $t= \max\left\lbrace\frac{d(p,p’)}{|p,p’|} \mid p,p’ \in P \right\rbrace$, where $d(p,p’)$ is the distance between two points in $G$ and $|p,p’|$ is the euclidean distance between $p$ and $p’$. A geometric spanner with dilation $t$ is also called a $t$-spanner.
Obviously, the complete graph with vertex set $P$ is a $1$-spanner for $P$. Thus, we consider the condition, that the edge set should be “not too big” formally. Common measures to analyse the quality of a spanner are the number of edges in $G$ or planarity. Further measures are total weight or maximum vertex degree, as all mentioned properties allow for more efficient algorithms on certain applications.
In graph theory, an important tool to design efficient algorithms for in general NP-hard problems is to regard these problems on graphs which are bounded in certain parameters as tree-width or clique-width. In our research we will consider spanners which are bounded by these parameters, which will allow the application of many graph theoretical results on geometric problems and especially allow efficient algorithms for many applications..