Tight bounds for fractional and randomized truthful schedulingResearch Paper
In scheduling on unrelated machines, tasks are assigned to machines, machine needs time for task , and the goal is to minimize the makespan, the largest total processing time of a machine. Nisan and Ronen proposed this as the canonical problem of algorithmic mechanism design (NR01): each machine privately knows its row and is paid by the…