9 citations · 19 across the 13 of their papers we have counts for
21 papers
Separating Measures by Hyperplanes
José Correa, Svenja M. Griesbach, Elfarouk Harb +4
Given red and blue points in , connect every red point to every blue point and weigh each segment by its length under a fixed norm. What fraction of the total weight…
Optimal Online Weighted Connectivity Augmentation
Mohit Garg, Felix Hommelsheim, Alexander Lindermayr
In the online Weighted Connectivity Augmentation Problem (WCAP), we are given a -edge-connected graph on vertices and a set of additional edges, called links, with nonnegati…
Tight Bounds for -Approximation for Minimum Spanning Trees in Doubling Metrics
Jan Höckendorff, Felix Hommelsheim, Christian Sohler +1
The minimum spanning tree (MST) problem is one of the most basic optimization problems on metric spaces and graphs. We study the problem of computing a -approximation to the…
Approximation Algorithms for Discounted Graph Search with Norm Objectives
Svenja M. Griesbach, Felix Hommelsheim, Max Klimm
We introduce a unified framework for classical search and routing problems, including pathwise search, expanding search, the minimum spanning tree problem, and the traveling salesp…
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…
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…
Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
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 i…
Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
Felix Hommelsheim, Zhenwei Liu, Nicole Megow +1
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, whi…
A Tight ()-Approximation Algorithm for Demand Strip Packing
Franziska Eberle, Felix Hommelsheim, Malin Rau +1
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 tha…
A -Approximation for Two-Edge Connectivity
Miguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni +3
The 2-Edge-Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected and unweighted graph, the task is to find a s…
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…
Accelerating Matroid Optimization through Fast Imprecise Oracles
Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr +3
Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus…
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…
Improved Approximation Algorithms for the Expanding Search Problem
Svenja M. Griesbach, Felix Hommelsheim, Max Klimm +1
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…
Matching Augmentation via Simultaneous Contractions
Mohit Garg, Felix Hommelsheim, Nicole Megow
We consider the matching augmentation problem (MAP), where a matching of a graph needs to be extended into a -edge-connected spanning subgraph by adding the minimum number of ed…
On the Complexity of Robust Bilevel Optimization With Uncertain Follower's Objective
Christoph Buchheim, Dorothee Henke, Felix Hommelsheim
We investigate the complexity of bilevel combinatorial optimization with uncertainty in the follower's objective, in a robust optimization approach. We show that the robust counter…
On the Complexity of the Bilevel Minimum Spanning Tree Problem
Christoph Buchheim, Dorothee Henke, Felix Hommelsheim
We consider the bilevel minimum spanning tree (BMST) problem where the leader and the follower choose a spanning tree together, according to different objective functions. By showi…
Fixed-Parameter Algorithms for Graph Constraint Logic
Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito +3
Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures \PSPACE\xsp…
Fault-Tolerant Edge-Disjoint Paths -- Beyond Uniform Faults
David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler +1
The overwhelming majority of survivable (fault-tolerant) network design models assume a uniform fault model. Such a model assumes that every subset of the network resources (edges…
Flexible Graph Connectivity: Approximating Network Design Problems Between 1- and 2-connectivity
David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler
Graph connectivity and network design problems are among the most fundamental problems in combinatorial optimization. The minimum spanning tree problem, the two edge-connected span…
How to Secure Matchings Against Edge Failures
Felix Hommelsheim, Moritz Mühlenthaler, Oliver Schaudt
Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We…