Journal article icon

Journal article

On the Nisan-Ronen conjecture

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 was a small constant. This note gives an overview of our recent paper that gives a lower bound of 1 + √n − 1.
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Publisher copy:
10.1145/3572885.3572888

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Association for Computing Machinery
Journal:
ACM SIGecom Exchanges More from this journal
Volume:
20
Issue:
1
Pages:
41-46
Publication date:
2022-11-28
DOI:
ISSN:
1551-9031
Language:
English
Keywords:
Pubs id:
1316817
Local pid:
pubs:1316817
Deposit date:
2023-05-10

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP