Conference item
A proof of the Nisan-Ronen conjecture
- Abstract:
- Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for n unrelated machines is n. This work validates the conjecture.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 547.7KB, Terms of use)
-
- Publisher copy:
- 10.1145/3564246.3585176
Authors
- Publisher:
- Association for Computing Machinery
- Host title:
- STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
- Pages:
- 672–685
- Publication date:
- 2023-06-02
- Acceptance date:
- 2023-02-06
- Event title:
- 55th Annual ACM Symposium on Theory of Computing (STOC 2023)
- Event location:
- Orlando, Florida, USA
- Event website:
- http://acm-stoc.org/stoc2023/index.html
- Event start date:
- 2023-06-20
- Event end date:
- 2023-06-23
- DOI:
- ISSN:
-
0737-8017
- ISBN:
- 9781450399135
- Language:
-
English
- Keywords:
- Pubs id:
-
1340593
- Local pid:
-
pubs:1340593
- Deposit date:
-
2023-08-06
- ARK identifier:
Terms of use
- Copyright holder:
- Christodoulou et al.
- Copyright date:
- 2023
- Rights statement:
- © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
- Notes:
- This is the author accepted manuscript. The final version is available online from Association for Computing Machinery at https://doi.org/10.1145/3564246.3585176
If you are the owner of this record, you can report an update to it here: Report update to this record