2 citations · 5 across the 17 of their papers we have counts for
4 papers · 1 filter
Non-Clairvoyant Scheduling with Progress Bars
Ziyad Benomar, Romain Cosson, Alexander Lindermayr +1
In non-clairvoyant scheduling, the goal is to minimize the total job completion time without prior knowledge of individual job processing times. This classical online optimization…
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…
A Little Clairvoyance Is All You Need
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Sh…
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…