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...
Главные авторы: | Christodoulou, G, Koutsoupias, E, Kovacs, A |
---|---|
Формат: | Journal article |
Язык: | English |
Опубликовано: |
Association for Computing Machinery
2022
|
Схожие документы
-
On the Nisan-Ronen conjecture
по: Christodoulou, G, и др.
Опубликовано: (2022) -
On the Nisan-Ronen conjecture for submodular valuations
по: Christodoulou, G, и др.
Опубликовано: (2020) -
A proof of the Nisan-Ronen conjecture
по: Christodoulou, G, и др.
Опубликовано: (2023) -
A proof of the Nisan-Ronen conjecture --- an overview
по: Christodoulou, G, и др.
Опубликовано: (2024) -
Comprehensive investigation of the Ronen method in slab geometry
по: Roy Gross, и др.
Опубликовано: (2023-02-01)