On the Nisan-Ronen conjecture

Christodoulou, George, Koutsoupias, Elias and Kovacs, Annamaria (2022) On the Nisan-Ronen conjecture. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022-2-7 - 2022-2-10.

Text
ontheNRconjectureCR.pdf - Author Accepted Manuscript
Download (342kB) | Preview

Official URL: http://dx.doi.org/10.1109/focs52979.2021.00086

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

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	mechanism design, algorithmic game theory
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	17 Nov 2021 09:32
Last Modified:	18 Jan 2023 21:24
DOI:	10.1109/FOCS52979.2021.00086
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3143303