A proof of the Nisan-Ronen conjecture --- an overview
This note presents an overview of our recent publication, which validates a conjecture proposed by Nisan and Ronen in their seminal paper [Nisan and Ronen 2001]. We show that the optimal approximation ratio for deterministic truthful mechanisms for makespan-minimization by a set of n unrelated machi...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2024
|