G. Christodoulou, E. Koutsoupias, and A.Kovacs.
Mechanism Design for Fractional Scheduling on Unrelated Machines.
ACM Transactions on Algorithms 6(2): (2010)
G. Christodoulou, E. Koutsoupias, and A. Kovacs.
Mechanism Design for Fractional Scheduling on Unrelated Machines.
ICALP 2007: 40-52
Abstract
In this paper, we consider the mechanism design version of the fractional variant of the scheduling problem on unrelated machines. We give a lower bound of 2-1/n for any fractional truthful mechanism, while we propose a truthful mechanism that achieves approximation of 1+(n-1)/2, for n machines. We also focus on an interesting family of allocation algorithms, the task-independent algorithms. We give a lower bound of 1+(n-1)/2, that holds for every (not only monotone) allocation algorithm of this class. Under this consideration, our truthful independent mechanism is the best that we can hope from this family of algorithms.Bib
@Article{CKK10,
author = {G. Christodoulou and E. Koutsoupias and A. Kov{\'a}cs},
title = {Mechanism Design for Fractional Scheduling on Unrelated Machines},
journal = {ACM Transactions on Algorithms},
volume = {6},
number = {2},
year = {2010},
ee = {http://doi.acm.org/10.1145/1721837.1721854},
}
@string{ICALP07 = {34th International Colloquium on Automata, Languages and Programming}}
@InProceedings{CKK07,
author = {G. Christodoulou and E. Koutsoupias and A. Kov{\'a}cs},
title = {Mechanism Design for Fractional Scheduling on Unrelated Machines},
booktitle = ICALP07,
pages = {40--52},
year = 2007,
month = {9-13 } #jul,
address = {Wroclaw, Poland},
}