On the Nisan-Ronen conjecture

11^th December 2020, 13:00
Giorgios Christodoulou
University of Liverpool

Abstract

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. In this talk we will discuss recent progress

towards validating the conjecture.

Additional Materials

• https://arxiv.org/pdf/2011.14434.pdf