Felix Hommelsheim

About Me: 

I am a postdoc at the Department of Mathematics and Computer Science at the University of Cologne, affiliated with Christian Sohler. 

My main research interest lies in the intersection of Theoretical Computer Science and Discrete Mathematics. I am interested in the design and analysis of approximation algorithms for graph problems, in particular network design.

I have received my PhD at TU Dortmund in 2020. My advisor was Christoph Buchheim. Subsequently, I was a postdoc at the University of Bremen under the supervision of Nicole Megow and at the Center for Mathematical Modelling in Santaigo de Chile, affiliated with Jose Soto and Jose Verschae.

e-mail: firstname.lastname [at] gmail [dot] com

News: 

• Our paper "Approximation Algorithms for Discounted Graph Search with Norm Objectives" (with Svenja Griesbach and Max Klimm) has been accepted at APPROX 2026.

• My paper "Improved Approximation Algorithms for Bounded-length Path Augmentation" has been accepted at APPROX 2026.

• My DFG Grant 573939419 "New Techniques and Improved Approximation Algorithms for Connectivity Augmentation Problems" got accepted! Hence, I can fund a PhD Position for 3 years. If you know someone who is looking for a PhD, please let me know!

• Our paper "Recoverable Robust Optimization with Commitment" (with Nicole Megow, Komal Muluk, and Britta Peis) has been published at Mathematical Programming.

• Our paper "A Complexity Dichotomy for Generalized Rainbow Matchings Based on Color Classes" (with Pia Jehmlich and Moritz Mühlenthaler) is now available on arxiv.

• Our paper "Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures" (with Zhenwei Liu, Nicole Megow, and Guochuan Zhang) has been accepted at SIDMA.

• Our paper "Improved Approximation Algorithms for the Expanding Search Problem" (with Svenja M. Griesbach, Max Klimm, and Kevin Schewior) has been accepted at SIDMA.

• I gave a talk on our paper "A Better-Than-5/4-Approximation for Two-Edge Connectivity" at SODA 2026 in Vancouver.

• In December 2025 I started a new postdoc at the University of Cologne, affiliated with Christian Sohler.

• Our paper "A Better-Than-5/4-Approximation for Two-Edge Connectivity"
  (with Alexander Lindermayr, and Zhenwei Liu) has been accepted at SODA 2026.

• Our paper "A 5/4-approximation for Two-Edge Connectivity" (with Miguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni, Afrouz Jabal Ameli, and Alexander Lindermayr) has been published at STOC 2025.