2 papers
cs.DS2023
Santa Claus meets Makespan and Matroids: Algorithms and Reductions
Étienne Bamas, Alexander Lindermayr, Nicole Megow +2
In this paper we study the relation of two fundamental problems in scheduling and fair allocation: makespan minimization on unrelated parallel machines and max-min fair allocation,…
cs.DS2022
Better Trees for Santa Claus
Étienne Bamas, Lars Rohwedder
We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes…