9 citations · 19 across the 13 of their papers we have counts for
5 papers · 1 filter
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…