Truthful Prompt Scheduling for Minimizing Sum of Completion Times
Alon Eden, Michal Feldman, Amos Fiat, Tzahi Taub · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
We give a prompt online mechanism for minimizing the sum of [weighted] completion times. This is the first prompt online algorithm for the problem. When such jobs are strategic agents, delaying scheduling decisions makes little sense. Moreover, the mechanism has a particularly simple form of an anonymous menu of options.