Showing 2025Show all
3 papers · 1 filter
cs.DS2025
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…
cs.DS2025
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…
cs.DS2025
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…