Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling
Sander Borst, Golnoosh Shahkarami, Rohit Vaish
We study interval scheduling from the perspective of fair allocation. There are identical machines and a set of intervals, each specified by a start time, an end time, and a no…
cs.DS2025
To buy or not to buy: deterministic rent-or-buy problems on node-weighted graphs
Sander Borst, Moritz Venzin
We study the rent-or-buy variant of the online Steiner forest problem on node- and edge-weighted graphs. For -node graphs with at most non-zero node-weights, and at mo…
cs.DS2024
Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
Sander Borst, Marek Eliáš, Moritz Venzin
We propose a -competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous b…