An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

Simple item page
dc.creatorLu, Pinyan
dc.creatorYu, Changyuan
dc.date2008-02-20
dc.date.accessioned2026-07-07T09:22:02Z
dc.date.available2026-07-07T09:22:02Z
dc.descriptionWe 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).
dc.identifierhttps://arxiv.org/abs/0802.2851
dc.identifierhttp://arxiv.org/abs/0802.2851
dc.identifierDans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/155238
dc.subjectData Structures and Algorithms
dc.titleAn Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines
dc.typetext

Files

Collections

arXiv