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: 

• 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.

• My paper "Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation" is now available on arxiv.

• 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.

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

• Our paper "A tight (3/2 + eps)-approximation for the Demand Strip Packing Problem" (with Franziska Eberle, Malin Rau, and Stefan Walzer) has been published at SODA 2025.