On the Nisan-Ronen conjecture
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 bo...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2022
|
| _version_ | 1797109541109760000 |
|---|---|
| author | Christodoulou, G Koutsoupias, E Kovacs, A |
| author_facet | Christodoulou, G Koutsoupias, E Kovacs, A |
| author_sort | Christodoulou, G |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T07:43:10Z |
| format | Journal article |
| id | oxford-uuid:e659e878-a5f1-40ad-bf73-4e94d6f91eb5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:43:10Z |
| publishDate | 2022 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:e659e878-a5f1-40ad-bf73-4e94d6f91eb52023-05-11T14:52:44ZOn the Nisan-Ronen conjectureJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:e659e878-a5f1-40ad-bf73-4e94d6f91eb5EnglishSymplectic ElementsAssociation for Computing Machinery2022Christodoulou, GKoutsoupias, EKovacs, AThe 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. |
| spellingShingle | Christodoulou, G Koutsoupias, E Kovacs, A On the Nisan-Ronen conjecture |
| title | On the Nisan-Ronen conjecture |
| title_full | On the Nisan-Ronen conjecture |
| title_fullStr | On the Nisan-Ronen conjecture |
| title_full_unstemmed | On the Nisan-Ronen conjecture |
| title_short | On the Nisan-Ronen conjecture |
| title_sort | on the nisan ronen conjecture |
| work_keys_str_mv | AT christodouloug onthenisanronenconjecture AT koutsoupiase onthenisanronenconjecture AT kovacsa onthenisanronenconjecture |