Search

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. ]> ) for Pm||C max (resp. P||C max ). [ABSTRACT FROM AUTHOR]

This paper is devoted to the following decremental problem. Initially, a graph and a distinguished subset of vertices, called initial group, are given. This group is connected by an initial tree. The decremental part of the input is given by an on-line sequence of withdrawals of vertices of the initial group, removed on-line one after one. The goal is to keep connected each successive group by a tree, satisfying a quality constraint: The maximum distance (called diameter) in each constructed tree must be kept in a given range compared to the best possible one. Under this quality constraint, our objective is to minimize the number of critical stages of the sequence of constructed trees. We call "critical" a stage where the current tree is rebuilt. We propose a strategy leading to at most O(logi) critical stages (i is the number of removed members). We also prove that there exist situations where Ω(logi) critical stages are necessary to any algorithm to maintain the quality constraint. Our strategy is then worst case optimal in order of magnitude. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling a sequence of intervals revealed on-line one by one in the order of their release dates on a set of k identical machines. Each interval i is associated with a processing time pi and a pair of arbitrary weights (wiA,wiB) and may be scheduled on one of the k identical machines or rejected. The objective is to determine a valid schedule maximizing the sum of the weights of the scheduled intervals for each coordinate. We first propose a generic on-line algorithm based on the combination of two monocriteria on-line algorithms and we prove that it gives rise to a pair of competitive ratios that are function of the competitive ratios of the monocriteria algorithms in the input. We apply this technique to the special case where wiA=1 and wiB=pi for every interval and as a corollary we obtain a pair of constant competitive ratios. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling on-line a sequence of degradable intervals in a set of k identical machines. Our objective is to find a schedule that maximizes simultaneously the Weight (equal to the sum of processing times) and the Size (equal to the number) of the scheduled intervals. We propose a bicriteria algorithm that uses the strategies of two monocriteria algorithms (GOL [7], maximizing the Size and LR [4], maximizing the Weight) and yields two simultaneous constant competitive ratios. This work is an extension of [2] (COCOON'04), where the same model of degradable intervals was investigated in an off-line context and the two objectives were considered separately. [ABSTRACT FROM AUTHOR]