4 papers
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…
Beyond the Half-Approximation: Fair and Efficient Online Class Matching
Sander Borst, Max Springer
Online bipartite matching, where agents are known in advance but items arrive sequentially and must be irrevocably assigned, is fundamental to problems ranging from ride-sharing to…
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…
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…