Journal article

A proof of the Nisan-Ronen conjecture --- an overview

Abstract:: This note presents an overview of our recent publication, which validates a conjecture proposed by Nisan and Ronen in their seminal paper [Nisan and Ronen 2001]. We show that the optimal approximation ratio for deterministic truthful mechanisms for makespan-minimization by a set of n unrelated machines is n.

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.
Share
Cite

Cite this record

APA Style

Christodoulou, G., Koutsoupias, E., & Kovacs, A. (2024). A proof of the Nisan-Ronen conjecture --- an overview. ACM SIGecom Exchanges, 21(1), 42–48.

MLA Style

Christodoulou, G, et al. “A Proof of the Nisan-Ronen Conjecture --- an Overview.” ACM SIGecom Exchanges, vol. 21, no. 1, 2024, pp. 42–48.

Chicago Style

Christodoulou, G, E Koutsoupias, and A Kovacs. 2024. “A Proof of the Nisan-Ronen Conjecture --- an Overview.” ACM SIGecom Exchanges 21 (1): 42–48.
Print

Access Document

Files:: Christodoulou_et_al_2023_A_proof_of.pdf

(Preview, Accepted manuscript, pdf, 327.5KB, Terms of use)

Publisher copy:: 10.1145/3699814.3699819

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:: 21
Issue:: 1
Pages:: 42-48
Publication date:: 2024-10-08
DOI:: 10.1145/3699814.3699819
EISSN:: 1551-9031

Language:: English
Keywords:: Nisan-Ronen conjecture

algorithmic mechanism design
Pubs id:: 2041464
Local pid:: pubs:2041464
Deposit date:: 2025-02-17
ARK identifier:: ark:/29072/ora_1757cff405a548eabff743b380b14abb

Terms of use

Copyright holder:: Christodoulou et al.
Copyright date:: 2024
Rights statement:: © 2024 Copyright is held by the owner/author(s).
Notes:: This is the accepted manuscript version of the article. The final version is available online from Association for Computing Machinery at https://dx.doi.org/10.1145/3699814.3699819

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