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: | , , |
|---|---|
| Formato: | Conference item |
| Idioma: | English |
| Publicado: |
IEEE
2022
|
| _version_ | 1826279008275267584 |
|---|---|
| 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 is still a small constant. This work makes progress towards validating the conjecture by showing a lower bound of 1+ ✓ n -1. |
| first_indexed | 2024-03-06T23:52:25Z |
| format | Conference item |
| id | oxford-uuid:730e8d8b-3da7-43f2-913a-484629a0920f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:52:25Z |
| publishDate | 2022 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:730e8d8b-3da7-43f2-913a-484629a0920f2022-03-26T19:54:02ZOn the Nisan-Ronen conjectureConference itemhttp://purl.org/coar/resource_type/c_5794uuid:730e8d8b-3da7-43f2-913a-484629a0920fEnglishSymplectic ElementsIEEE2022Christodoulou, 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 is still a small constant. This work makes progress towards validating the conjecture by showing 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 |