On the Nisan-Ronen conjecture

The Nisan-Ronen conjecture states that no truthful mechanism for makespan-minimization when allocating m tasks to n unrelated machines can have approximation ratio less than n. Over more than two decades since its formulation, little progress has been made in resolving it and the best known lower bo...

תיאור מלא

מידע ביבליוגרפי
Main Authors: Christodoulou, G, Koutsoupias, E, Kovacs, A
פורמט: Journal article
שפה:English
יצא לאור: Association for Computing Machinery 2022
Search Result 1

On the Nisan-Ronen conjecture מאת Christodoulou, G, Koutsoupias, E, Kovacs, A

יצא לאור 2022
Conference item