9 citations · 19 across the 13 of their papers we have counts for
3 papers · 2 filters
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…