4 papers
Polytope Scheduling with Groups: Unified Models and Optimal Guarantees
Alexander Lindermayr, Zhenwei Liu, Nicole Megow
We propose new abstract and unified perspectives on a range of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider various problems wh…
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…
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…
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…