# On the Nisan-Ronen conjecture

arXiv: https://arxiv.org/abs/2011.14434 · HTML: https://mlsanity.com/paper/2011.14434/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2020.

## Built on by (most cited first, 1 of 1)

- [On Scheduling Mechanisms Beyond the Worst Case](https://mlsanity.com/paper/2204.07223/) (2022)

## Abstract (arXiv)

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 bound is still a small constant. This work makes progress towards validating the conjecture by showing a lower bound of 1+√n-1.