Makespan Minimization via Posted Prices

Michal Feldman, Amos Fiat, Alan Roytman

We consider job scheduling settings, with multiple machines, where jobs arrive online and choose a machine selfishly so as to minimize their cost. Our objective is the classic make…