Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Tobias Mömke

Tobias Mömkke Address:
Universität des Saarlandes
Tobias Mömke
Campus Geb E13
Postfach 42 (Bläser)
66123 Saarbrücken

Office: Building E1 3, Room 422
Phone: +49 681 302-5502
Email: "moemke" at ""

Researcher in theoretical computer science (DFG eigene Stelle)

Optimization is important in our every day lives, in industrial applications and in applications with global impact. We rely on navigation systems to find our way. Delivery services have to find efficient routes to deliver their goods as fast and fuel-efficient as possible. Politicians have to decide on tax rates in order to maximize the social welfare.

While some optimization problems can be solved efficiently, there are many relevant optimization problems that are computationally hard. Among these, NP-hard optimization problems such as the traveling salesperson problem and the Steiner tree problem play a prominent role. These problems have a number of real life applications. Even though these problems are computationally hard, finding useful solutions is oftentimes possible.

My research aims to develop new algorithmic approaches for NP-hard optimization problems. My aim is to use and develop elegant and clean techniques from combinatorial optimization, with a special focus on linear programming and related advanced methods. Such results have the potential to be simple enough for practical uses. I believe that providing algorithms with theoretically proven performances is a powerful way to improve our understanding of the sources of hardness and to identify the algorithmic properties that lead to efficient computation.

Short CV

10/2018 - present
DFG Eigene Stelle, Saarland University, Germany

10/2017 - 09/2018
Interim Professor (Theoretical Computer Science),
University of Bremen, Germany

10/2015 - 09/2017
DFG Eigene Stelle, Saarland University, Germany

09/2012 - 10/2015
Postdoc, Saarland University, Germany

11/2010 - 08/2012
Postdoc, KTH Royal Institute of Technology, Sweden

02/2010 - 10/2010
Postdoc, ETH Zurich, Switzerland

Doctor of Sciences ETH Zurich, Switzerland

Diplom-Informatiker (Equivalent to MSc.),
RWTH Aachen, Germany

Erasmus Exchange Program, Universidad Politécnica de Valencia, Spain


DFG Project "Neuartige Approximationstechniken für Traveling Salesperson Probleme"

Program Committee Member

Advances in Reoptimization and Dynamic Algorithms (ARDA 2019)

19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016)


Summer term 2018 at University of Bremen.

Winter term 2017/18 at University of Bremen.

2017 at Saarland University:

2016: Lecture series on Approximation Algorithms at "Workshop on Algorithmics for Hard Problems," UP Diliman, Philippines

2014: "Selected Topics in Combinatorial Optimization" at Saarland University

2012: FDD3402 Combinatorial Optimization at KTH - Royal Institute of Technology, Stockholm, Sweden


Journal Publications

Refereed Conference Publications

Selected Technical Reports


Last updated: 2019-02-21