{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:42:30Z","timestamp":1773481350686,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["IST-2005-15964 (AEOLUS)IST-2008-215270 (FRONTS)"],"award-info":[{"award-number":["IST-2005-15964 (AEOLUS)IST-2008-215270 (FRONTS)"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>Scheduling on unrelated machines is one of the most general and classical variants of the task scheduling problem. Fractional scheduling is the LP-relaxation of the problem, which is polynomially solvable in the nonstrategic setting, and is a useful tool to design deterministic and randomized approximation algorithms.<\/jats:p>\n          <jats:p>\n            The mechanism design version of the scheduling problem was introduced by Nisan and Ronen. In this article, we consider the mechanism design version of the fractional variant of this problem. We give lower bounds for any fractional truthful mechanism. Our lower bounds also hold for any (randomized) mechanism for the integral case. In the positive direction, we propose a truthful mechanism that achieves approximation 3\/2 for 2 machines, matching the lower bound. This is the first new tight bound on the approximation ratio of this problem, after the tight bound of 2, for 2 machines, obtained by Nisan and Ronen. For\n            <jats:italic>n<\/jats:italic>\n            machines, our mechanism achieves an approximation ratio of\n            <jats:italic>n<\/jats:italic>\n            +1\/2.\n          <\/jats:p>\n          <jats:p>\n            Motivated by the fact that all the known deterministic and randomized mechanisms for the problem assign each task independently from the others, we focus on an interesting subclass of allocation algorithms, the\n            <jats:italic>task-independent<\/jats:italic>\n            algorithms. We give a lower bound of\n            <jats:italic>n<\/jats:italic>\n            +1\/2, that holds for every (not only monotone) allocation algorithm that takes independent decisions. Under this consideration, our truthful independent mechanism is the best that we can hope from this family of algorithms.\n          <\/jats:p>","DOI":"10.1145\/1721837.1721854","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Mechanism design for fractional scheduling on unrelated machines"],"prefix":"10.1145","volume":"6","author":[{"given":"George","family":"Christodoulou","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}]},{"given":"Elias","family":"Koutsoupias","sequence":"additional","affiliation":[{"name":"University of Athens, Athens, Greece"}]},{"given":"Annam\u00e1ria","family":"Kov\u00e1cs","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}]}],"member":"320","published-online":{"date-parts":[[2010,4,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_6"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 205--214","author":"Archer A.","year":"2003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875583"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference (AAAI). 241--247","author":"Babaioff M."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846250"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2006.00695.x"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060597"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP). 40--52","author":"Christodoulou G."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 1163--1170","author":"Christodoulou G."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060681"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132607"},{"key":"e_1_2_1_13_1","unstructured":"Gui H. M\u00fcller R. and Vohra R. V. 2005. Dominant strategy mechanisms with multidimensional types. In Computing and Markets.  Gui H. M\u00fcller R. and Vohra R. V. 2005. Dominant strategy mechanisms with multidimensional types. In Computing and Markets."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_55"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS). 574--583","author":"Lavi R."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.76"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250947"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1143--1152","author":"Mu'alem A."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301287"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064040"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721854","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1721837.1721854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:38Z","timestamp":1750249418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721854"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1721837.1721854"],"URL":"https:\/\/doi.org\/10.1145\/1721837.1721854","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2007-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}