Ee, Martijn van 2
Logistics & Operations Research

Dissertation title
Routing under Uncertainty: Approximation and Complexity

Date and location
December 6, 2017 at 13:45 in the Aula of the Main Building of the Vrije Universiteit Amsterdam

Routing under Uncertainty: Approximation and Complexity

Ee, Martijn vanWe study the approximability and complexity of routing problems under uncertainty. In routing problems, we have to walk through a graph while optimizing some objective. For example, in the traveling salesman problem (TSP) we have to visit all vertices in the graph using a tour of minimum length. Another example is the traveling repairman problem (TRP), where we want to minimize the total latency. In this thesis, we consider two types of routing problems under uncertainty: a priori routing and graph search.

In a priori routing only a subset of the vertices of the graph needs to be visited but this subset is unknown. However, we need to make just one tour on all vertices called the first-stage tour. After that, the set of vertices to be visited, the active set, is revealed. The second-stage tour can now be derived by shortcutting the first-stage tour to the active set. If we are given a probability distribution over the active sets, we can compute the expected cost of the second-stage tour. Now, our goal is to construct a tour minimizing this expectation. We give complexity and hardness result for the a priori TSP. Also, we obtained a constant-factor approximation for a priori TRP.

In the graph search problem, there is a target hidden at a vertex in the graph and one has to find it. We are given a probability distribution and our goal is to find a walk that minimizes the expected length until finding the target. We consider generalizations to multiple targets, failing edges and non-discrete probability distributions. Here, we also obtain results on hardness and derive approximation algorithms.

Short biography
Martijn van Ee (1991) obtained his BSc degree (cum laude) in Econometrics and Operations Research in 2012 at the University of Amsterdam. In 2013, he obtained his MSc degree (cum laude) in Econometrics and Operations Research at the Vrije Universiteit Amsterdam. In January 2014, he started a PhD program in the field of combinatorial optimization under supervision of René Sitters and prof.dr. Leen Stougie. In January 2018, Martijn will start as an assistant professor at the Netherlands Defence Academy. His research interests include approximation algorithms and computational complexity.