A proof of the Nisan-Ronen conjecture

George Christodoulou, Elias Koutsoupias, Annamaria Kovacs

Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for $n$ unrelated machines is $n$. This work…