ELIAS KOUTSOUPIAS: The Nisan-Ronen Conjecture

Seminars - CS seminar series
Speakers
ELIAS KOUTSOUPIAS, Oxford university
12:00 - 13:00
Room 3-E4-SR03 (Roentgen) / Zoom
seminar

Abstract: 

 

The Nisan-Ronen conjecture, a central problem in algorithmic game theory, states that no truthful mechanism for makespan-minimization when allocating a set of tasks to n unrelated machines can have approximation ratio less than n. Since the class of truthful mechanisms is exactly the class of monotone algorithms, validating the conjecture would provide a strong separation between monotone and non-monotone optimization algorithms. In this talk, I will discuss recent progress on this conjecture. The results are based on studying an interesting special class of instances that can be represented by multi-graphs in which vertices represent machines and edges represent tasks, and each task should be allocated to one of its two incident machines.

 

In order to receive the Zoom link of the event , please write to giovanni.tardino@unibocconi.it