3 papers
cs.DS2026
Online Flexible Busy Time Scheduling on Heterogeneous Machines
Gruia Calinescu, Sami Davies, Samir Khuller +1
We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform length arrive online with a deadline that becomes known to the algorithm…
cs.DS2026
A Tale of Santa Claus, Hypergraphs and Matroids
Sami Davies, Thomas Rothvoss, Yihao Zhang
A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set…
cs.DS2025
Scheduling Problems with Constrained Rejections
Sami Davies, Venkatesan Guruswami, Xuandi Ren
We study bicriteria versions of Makespan Minimization on Unrelated Machines and Santa Claus by allowing a constrained number of rejections. Given an instance of Makespan Minimizati…