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

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Cite

Cite this record

APA Style

Christodoulou, G., Koutsoupias, E., & Kovacs, A. (2022). On the Nisan-Ronen conjecture. ACM SIGecom Exchanges, 20(1), 41–46.

MLA Style

Christodoulou, G., et al. “On the Nisan-Ronen Conjecture.” ACM SIGecom Exchanges, vol. 20, no. 1, Association for Computing Machinery, 2022, pp. 41–46.

Chicago Style

Christodoulou, G, E Koutsoupias, and A Kovacs. 2022. “On the Nisan-Ronen Conjecture.” ACM SIGecom Exchanges 20 (1): 41–46.
Share
Print

Access Document

Publisher copy:: 10.1145/3572885.3572888

Authors

+ Christodoulou, G More by this author

Role:: Author

+ Koutsoupias, E More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Role:: Author

+ Kovacs, A More by this author

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:: 10.1145/3572885.3572888
ISSN:: 1551-9031

Language:: English
Keywords:: algorithmic mechanism design

FFR

Nisan-Ronen conjecture
Pubs id:: 1316817
Local pid:: pubs:1316817
Deposit date:: 2023-05-10

Terms of use

Copyright holder:: Christodoulou et al.
Copyright date:: 2022
Rights statement:: Copyright © 2022 Copyright is held by the owner/author(s).

Licence:: Terms and Conditions of Use for Oxford University Research Archive

Views and Downloads

About 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