{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:24Z","timestamp":1750309464432,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGecom Exch."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:p>\n            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            <jats:italic>n<\/jats:italic>\n            unrelated machines is\n            <jats:italic>n.<\/jats:italic>\n          <\/jats:p>","DOI":"10.1145\/3699814.3699819","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T16:30:17Z","timestamp":1728405017000},"page":"42-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Proof of the Nisan-Ronen Conjecture --- An Overview"],"prefix":"10.1145","volume":"21","author":[{"given":"George","family":"Christodoulou","sequence":"first","affiliation":[{"name":"Aristotle University of Thessaloniki and Archimedes\/RC Athena"}]},{"given":"Elias","family":"Koutsoupias","sequence":"additional","affiliation":[{"name":"University of Oxford"}]},{"given":"Annamaria","family":"Kovacs","sequence":"additional","affiliation":[{"name":"Goethe University, Frankfurt M."}]}],"member":"320","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"volume-title":"Truthful mechanisms for one-parameter agents","author":"Archer A.","key":"e_1_2_1_1_1","unstructured":"Archer, A. and Tardos, \u00c9. 2001. Truthful mechanisms for one-parameter agents. In FOCS. IEEE Computer Society, 482--491."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721854"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Christodoulou G. Koutsoupias E. and Kov\u00e1cs A. 2021a. On the Nisan-Ronen conjecture. In FOCS. IEEE 839--850.","DOI":"10.1109\/FOCS52979.2021.00086"},{"key":"e_1_2_1_4_1","first-page":"1","article-title":"Truthful allocation in graphs and hypergraphs","volume":"198","author":"Christodoulou G.","year":"2021","unstructured":"Christodoulou, G., Koutsoupias, E., and Kov\u00e1cs, A. 2021b. Truthful allocation in graphs and hypergraphs. In ICALP. LIPIcs, vol. 198. 56:1--56:20.","journal-title":"ICALP. LIPIcs"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Christodoulou G. Koutsoupias E. and Kov\u00e1cs A. 2023. A proof of the Nisan-Ronen conjecture. In STOC. ACM 672--685.","DOI":"10.1145\/3564246.3585176"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1668926.1668927"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/120866038"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Clarke E. H. 1971. Multipart pricing of public goods. Public Choice 8.","DOI":"10.1007\/BF01726210"},{"key":"e_1_2_1_9_1","unstructured":"Dobzinski S. and Shaulker A. 2020. Improved Lower Bounds for Truthful Scheduling."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00847-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Koutsoupias E. and Vidali A. 2012. A lower bound of 1+\u03c6 for truthful scheduling mechanisms. Algorithmica 1--13.","DOI":"10.1007\/s00453-012-9634-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.02.001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3699814.3699819","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3699814.3699819","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:33Z","timestamp":1750295433000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3699814.3699819"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10.1145\/3699814.3699819"],"URL":"https:\/\/doi.org\/10.1145\/3699814.3699819","relation":{},"ISSN":["1551-9031"],"issn-type":[{"type":"electronic","value":"1551-9031"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"2024-10-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}