Felix Hommelsheim

Felix Hommelsheim

Auto-generated profile, based on publicly available information

Felix Hommelsheim

University of Bremen, Bremen, Germany

Research Focus & Metrics

Academic Career Length

3Years (2024-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 June 2025
Verified
Conference Paper
Open access
MBMiguel Bosch-Calvo
Miguel Bosch-Calvo
MGMohit Garg
Mohit Garg
FGFabrizio Grandoni
Fabrizio Grandoni
FHFelix Hommelsheim
Felix Hommelsheim
AAAfrouz Jabal Ameli
Afrouz Jabal Ameli
ALAlexander Lindermayr
Alexander Lindermayr

16 August 2024 in arXiv
Verified
Preprint
Open access
PDF file
FEFranziska Eberle
Franziska Eberle
FHFelix Hommelsheim
Felix Hommelsheim
MRMalin Rau
Malin Rau
SWStefan Walzer
Stefan Walzer
We consider the Demand Strip Packing problem (DSP), in which we are given a set of jobs, each specified by a processing time and a demand. The task is to schedule all jobs such that they are finished before some deadline $D$ while minimizing the peak demand, i.e., the maximum total demand of tasks executed at any point in time. DSP is closely related to the Strip Packing problem (SP), in which we are given a set of axis-aligned rectangles that must be packed into a strip of fixed width while minimizing the maximum height. DSP and SP are known to be NP-hard to approximate to within a factor below $\frac{3}{2}$. To achieve the essentially best possible approximation guarantee, we prove a structural result. Any instance admits a solution with peak demand at most $\big(\frac32+\varepsilon\big)OPT$ satisfying one of two properties. Either (i) the solution leaves a gap for a job with demand $OPT$ and processing time $\mathcal O(\varepsilon D)$ or (ii) all jobs with demand greater than $\frac{OPT}2$ appear sorted by demand in immediate succession. We then provide two efficient algorithms that find a solution with maximum demand at most $\big(\frac32+\varepsilon\big)OPT$ in the respective case. A central observation, which sets our approach apart from previous ones for DSP, is that the properties (i) and (ii) need not be efficiently decidable: We can simply run both algorithms and use whichever solution is the better one.

17 March 2026 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
SGSvenja M. Griesbach
Svenja M. Griesbach
FHFelix Hommelsheim
Felix Hommelsheim
MKMax Klimm
Max Klimm
KSKevin Schewior
Kevin Schewior
A searcher is tasked with exploring a graph with edge lengths and vertex weights, starting from a designated vertex. Initially, only the starting vertex is considered explored. At each step, the searcher adds an edge to the solution, connecting an unexplored vertex to an explored one. The time required to add an edge equals its length. The objective is to minimize the weighted sum of exploration times for all vertices. We demonstrate that this problem is hard to approximate and present algorithms with improved approximation guarantees. Specifically, we provide a [Formula: see text]-approximation for any [Formula: see text] for the general case. On instances where the vertex weights are binary, we achieve a [Formula: see text]-approximation. Finally, we develop a polynomial-time approximation scheme for Euclidean graphs. Previously, only an 8-approximation was known for all these cases.

23 July 2026 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
FHFelix Hommelsheim
Felix Hommelsheim
ZLZhenwei Liu
Zhenwei Liu
NMNicole Megow
Nicole Megow
GZGuochuan Zhang
Guochuan Zhang
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a nonuniform failure model. We introduce the [Formula: see text]-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains [Formula: see text]-edge-connectivity between given terminal pairs against edge failures, assuming at most [Formula: see text] unprotected edges can fail. We design polynomial-time exact algorithms for the cases where [Formula: see text] and [Formula: see text] are small and approximation algorithms for general values of [Formula: see text] and [Formula: see text]. Additionally, we show that when both [Formula: see text] and [Formula: see text] are part of the input, even deciding whether a given solution is feasible is [Formula: see text]-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either [Formula: see text] or [Formula: see text] is constant, for which our new hardness result now provides justification.

21 May 2025 in arXiv
Verified
Preprint
Open access
PDF file
FHFelix Hommelsheim
Felix Hommelsheim
The Forest Augmentation Problem (FAP) asks for a minimum set of additional edges (links) that make a given forest 2-edge-connected while spanning all vertices. A key special case is the Path Augmentation Problem (PAP), where the input forest consists of vertex-disjoint paths. Grandoni, Jabal Ameli, and Traub [STOC'22] recently broke the long-standing 2-approximation barrier for FAP, achieving a 1.9973-approximation. A crucial component of this result was their 1.9913-approximation for PAP; the first better-than-2 approximation for PAP. In this work, we improve these results and provide a 1.9412-approximation for PAP, which implies a 1.9955-approximation for FAP. One of our key innovations is a $(\frac{7}{4} + \varepsilon)$-approximation preserving reduction to so-called structured instances, which simplifies the problem and enables our improved approximation. Additionally, we introduce a new relaxation inspired by 2-edge covers and analyze it via a corresponding packing problem, where the relationship between the two problems is similar to the relationship between 2-edge covers and 2-matchings. Using a factor-revealing LP, we bound the cost of our solution to the packing problem w.r.t. the relaxation and derive a strong initial solution. We then transform this solution into a feasible PAP solution, combining techniques from FAP and related connectivity augmentation problems, along with new insights. A key aspect of our approach is leveraging the properties of structured PAP instances to achieve our final approximation guarantee. Our reduction framework and relaxation may be of independent interest in future work on connectivity augmentation problems.