{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:13:46Z","timestamp":1750220026436,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"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":[[2022,7]]},"abstract":"<jats:p>\n            The Nisan-Ronen conjecture states that no truthful mechanism for makespan-minimization when allocating\n            <jats:italic>m<\/jats:italic>\n            tasks to\n            <jats:italic>n<\/jats:italic>\n            unrelated machines can have approximation ratio less than\n            <jats:italic>n.<\/jats:italic>\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 [EQUATION].\n          <\/jats:p>","DOI":"10.1145\/3572885.3572888","type":"journal-article","created":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T17:05:57Z","timestamp":1669655157000},"page":"41-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On the nisan-ronen conjecture"],"prefix":"10.1145","volume":"20","author":[{"given":"George","family":"Christodoulou","sequence":"first","affiliation":[{"name":"Aristotle University of Thessaloniki"}]},{"given":"Elias","family":"Koutsoupias","sequence":"additional","affiliation":[{"name":"University of Oxford"}]},{"given":"Annamaria","family":"Kovacs","sequence":"additional","affiliation":[{"name":"Goethe University"}]}],"member":"320","published-online":{"date-parts":[[2022,11,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Archer A. and Kleinberg R. 2008. Truthful germs are contagious: a local to global characterization of truthfulness. In EC. ACM 21--30.  Archer A. and Kleinberg R. 2008. Truthful germs are contagious: a local to global characterization of truthfulness. In EC. ACM 21--30.","DOI":"10.1145\/1386790.1386796"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2006.00695.x"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721854"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Christodoulou G. Koutsoupias E. and Kov\u00e1cs A. 2020. On the Nisan-Ronen conjecture for submodular valuations. In STOC. ACM 1086--1096. (Full version arXiv:1907.12733).  Christodoulou G. Koutsoupias E. and Kov\u00e1cs A. 2020. On the Nisan-Ronen conjecture for submodular valuations. In STOC. ACM 1086--1096. (Full version arXiv:1907.12733).","DOI":"10.1145\/3357713.3384299"},{"key":"e_1_2_1_5_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.  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_6_1","unstructured":"Christodoulou G. Koutsoupias E. and Kov\u00e1cs A. 2021b. Truthful allocation in graphs and hypergraphs. In ICALP. Vol. 198. 56:1--56:20.  Christodoulou G. Koutsoupias E. and Kov\u00e1cs A. 2021b. Truthful allocation in graphs and hypergraphs. In ICALP. Vol. 198. 56:1--56:20."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1668926.1668927"},{"key":"e_1_2_1_8_1","unstructured":"Dobzinski S. and Shaulker A. 2020. Improved Lower Bounds for Truthful Scheduling.  Dobzinski S. and Shaulker A. 2020. Improved Lower Bounds for Truthful Scheduling."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Giannakopoulos Y. Hammerl A. and Po\u00e7as D. 2020. A new lower bound for deterministic truthful scheduling. In SAGT. Vol. 12283. 226--240.  Giannakopoulos Y. Hammerl A. and Po\u00e7as D. 2020. A new lower bound for deterministic truthful scheduling. In SAGT. Vol. 12283. 226--240.","DOI":"10.1007\/978-3-030-57980-7_15"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Koutsoupias E. and Vidali A. 2012. A lower bound of 1+\u03d5 for truthful scheduling mechanisms. Algorithmica 1--13.  Koutsoupias E. and Vidali A. 2012. A lower bound of 1+\u03d5 for truthful scheduling mechanisms. Algorithmica 1--13.","DOI":"10.1007\/s00453-012-9634-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Lenstra J. K. Shmoys D. B. and Tardos E. 1990. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming 46 1--3 259--271.  Lenstra J. K. Shmoys D. B. and Tardos E. 1990. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming 46 1--3 259--271.","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.02.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Nisan N. Roughgarden T. Tardos E. and Vazirani V. V. 2007. Algorithmic Game Theory. Cambridge University Press.  Nisan N. Roughgarden T. Tardos E. and Vazirani V. V. 2007. Algorithmic Game Theory. Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Saks M. E. and Yu L. 2005. Weak monotonicity suffices for truthfulness on convex domains. In EC. ACM 286--293.  Saks M. E. and Yu L. 2005. Weak monotonicity suffices for truthfulness on convex domains. In EC. ACM 286--293.","DOI":"10.1145\/1064009.1064040"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3572885.3572888","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3572885.3572888","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:38Z","timestamp":1750182698000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3572885.3572888"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.1145\/3572885.3572888"],"URL":"https:\/\/doi.org\/10.1145\/3572885.3572888","relation":{},"ISSN":["1551-9031"],"issn-type":[{"type":"electronic","value":"1551-9031"}],"subject":[],"published":{"date-parts":[[2022,7]]},"assertion":[{"value":"2022-11-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}