Truthful Approximation Mechanisms for Scheduling Selfish Related Machines |
| |
Authors: | Nir Andelman Yossi Azar Motti Sorani |
| |
Affiliation: | (1) Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel |
| |
Abstract: | We consider the problem of scheduling jobs on related machines owned by selfish agents. We provide a 5-approximation deterministic
truthful mechanism, the first deterministic truthful result for the problem. Previously, Archer and Tardos showed a 2-approximation
randomized mechanism which is truthful in expectation only (a weaker notion of truthfulness). In case the number of machines
is constant, we provide a deterministic Fully Polynomial-Time Approximation Scheme (FPTAS) and a suitable payment scheme that
yields a truthful mechanism for the problem. This result, which is based on converting FPTAS to monotone FPTAS, improves a
previous result of Auletta et al., who showed a (4 + ε)-approximation truthful mechanism. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|