Portal de Periódicos da CAPES

Randomized Truthful Algorithms for Scheduling Selfish Tasks on Parallel Machines

2010; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-642-12200-2_5

1611-3349

Éric Angel, Evripidis Bampis, Nicolas Thibault,

Complexity and Algorithms in Graphs

We study the problem of designing truthful algorithms for scheduling a set of tasks, each one owned by a selfish agent, to a set of parallel (identical or unrelated) machines in order to minimize the makespan. We consider the following process: at first the agents declare the length of their tasks, then given these bids the protocol schedules the tasks on the machines. The aim of the protocol is to minimize the makespan, i.e. the maximal completion time of the tasks, while the objective of each agent is to minimize the completion time of its task and thus an agent may lie if by doing so, his task may finish earlier. In this paper, we show the existence of randomized truthful (non-polynomial-time) algorithms with expected approximation ratio equal to 3/2 for different scheduling settings (identical machines with and without release dates and unrelated machines) and models of execution (strong or weak). Our result improves the best previously known result [1] for the problem with identical machines (P||C max ) in the strong model of execution and reaches, asymptotically, the lower bound of [5]. In addition, this result can be transformed to a polynomial-time truthful randomized algorithm with expected approximation ratio 3/2 + ε (resp. $\frac{11}{6}-\frac{1}{3m}$ ) for Pm||C max (resp. P||C max ).