A proof of the Nisan-Ronen conjecture
Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for <i>n</i> unrelated machines is <i>n</i>. This work validates the conjecture.
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for Computing Machinery
2023
|