排序方式: 共有1条查询结果,搜索用时 0 毫秒
1
1.
Eric Angel Evripidis Bampis Fanny Pascual Alex-Ariel Tchetgnia 《Journal of Scheduling》2009,12(5):437-445
We consider the problem of designing truthful mechanisms for scheduling n tasks on a set of m parallel related machines in order to minimize the makespan. In what follows, we consider that each task is owned by a selfish
agent. This is a variant of the KP-model introduced by Koutsoupias and Papadimitriou (Proc. of STACS 1999, pp. 404–413, 1999) (and of the CKN-model of Christodoulou et al. in Proc. of ICALP 2004, pp. 345–357, 2004) in which the agents cannot choose the machine on which their tasks will be executed. This is done by a centralized authority,
the scheduler. However, the agents may manipulate the scheduler by providing false information regarding the length of their
tasks. We introduce the notion of increasing algorithm and a simple reduction that transforms any increasing algorithm into
a truthful one. Furthermore, we show that some of the classical scheduling algorithms are indeed increasing: the LPT algorithm,
the PTAS of Graham (SIAM J. Appl. Math. 17(2):416–429, 1969) in the case of two machines, as well as a simple PTAS for the case of m machines, with m a fixed constant. Our results yield a randomized r(1+ε)-approximation algorithm where r is the ratio between the largest and the smallest speed of the related machines. Furthermore, by combining our approach with
the classical result of Shmoys et al. (SIAM J. Comput. 24(6):1313–1331, 1995), we obtain a randomized 2r(1+ε)-competitive algorithm. It has to be noticed that these results are obtained without payments, unlike most of the existing
works in the field of Mechanism Design. Finally, we show that if payments are allowed then our approach gives a (1+ε)-algorithm for the off-line case with related machines. 相似文献
1