From the 2 of 10 linked papers with an AI index.
3 citations · 3 across the 3 of their papers we have counts for
10 papers
A Fast and Simple -Approximation for Minimum Spanning Trees in Doubling Metrics
Jan Höckendorff, Jan Höckendorff, Felix Hommelsheim +2
The paper presents a deterministic algorithm that computes a (1+ε)-approximation of the minimum spanning tree in metric spaces with bounded doubling dimension, achieving a runtime…
Approximation Algorithms for Discounted Graph Search with Norm Objectives
Svenja M. Griesbach, Felix Hommelsheim, Max Klimm
The paper proposes a unified model for graph search and routing problems that incorporates discounted edge costs and a p‑norm objective, and provides constant‑factor approximation…
Recoverable Robust Optimization with Commitment
Felix Hommelsheim, Nicole Megow, Komal Muluk +1
We propose a model for recoverable robust optimization with commitment. Given a combinatorial optimization problem and uncertainty about elements that may fail, we ask for a robust…
A Complexity Dichotomy for Generalized Rainbow Matchings Based on Color Classes
Felix Hommelsheim, Pia Jehmlich, Moritz Mühlenthaler
Given an edge-colored graph, the Maximum Rainbow Matching problem asks for a maximum-cardinality matching of the graph that contains at most one edge from each color. We provide th…
Two-Edge Connectivity via Pac-Man Gluing
Mohit Garg, Felix Hommelsheim, Alexander Lindermayr
We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph , compute a connected subgraph of with the minimum number of edges such that is spann…
A Better-Than--Approximation for Two-Edge Connectivity
Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu
The 2-Edge-Connected Spanning Subgraph Problem (2ECSS) is a fundamental problem in survivable network design. Given an undirected -edge-connected graph, the goal is to find a $2…