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.
| Päätekijät: | , , |
|---|---|
| Aineistotyyppi: | Conference item |
| Kieli: | English |
| Julkaistu: |
Association for Computing Machinery
2023
|