2026-07-22T11:59:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1314 2024-03-06T10:33:01Z ddc:004 open_access

An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines Lu, Pinyan Yu, Changyuan Truthful mechanism scheduling We study the scheduling problem on unrelated machines in the mechanism design setting. This problem was proposed and studied in the seminal paper (Nisan and Ronen 1999), where they gave a $1.75$-approximation randomized truthful mechanism for the case of two machines. We improve this result by a $1.6737$-approximation randomized truthful mechanism. We also generalize our result to a $0.8368m$-approximation mechanism for task scheduling with $m$ machines, which improve the previous best upper bound of $0.875m( Mu'alem and Schapira 2007) Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pinyan Lu and Changyuan Yu 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1314 urn:nbn:de:0030-drops-13146 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1314 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode