hide
Free keywords:
-
Abstract:
We present a unified framework for designing deterministic monotone polynomial
time approximation schemes (PTAS's) for a wide class of scheduling problems on
uniformly related machines. This class includes (among others) minimizing the
makespan, maximizing the minimum load, and minimizing the ℓ_p norm of the
machine loads vector. Previously, this kind of result was only known for the
makespan objective. Monotone algorithms have the property that an increase in
the speed of a machine cannot decrease the amount of work assigned to it.
The key idea of our novel method is to show that for goal functions that are
sufficiently well-behaved functions of the machine loads, it is possible to
compute in polynomial time a highly
structured nearly optimal schedule.
An interesting aspect of our approach is that, in contrast to all known
approximation schemes, we avoid rounding any job sizes or speeds throughout. We
can therefore find the \emphexact} best structured schedule using dynamic
programming. The state space encodes a sufficient amount of information such
that no postprocessing is needed, allowing an elegant and relatively simple
analysis without any special cases. The monotonicity is a consequence of the
fact that we find the {\it best schedule in a specific collection of schedules.
Monotone approximation schemes have an important role in the emerging area of
algorithmic mechanism design.
In the game-theoretical setting of these scheduling problems there is a social
goal, which is one of the objective functions that we study. Each machine is
controlled by a selfish single-parameter agent, where its private information
is its cost of processing a unit sized job, which is also the inverse of
the speed of its machine. Each agent wishes to maximize its own profit, defined
as the payment it receives from the mechanism minus its cost for processing all
jobs assigned to it, and places a bid which corresponds to its private
information.
For each one of the problems, we show that we can calculate payments that
guarantee truthfulness in an efficient manner. Thus, there exists a dominant
strategy where agents report their true speeds, and we show the existence of a
truthful mechanism which can be implemented in polynomial time, where the
social goal is approximated within a factor of 1+\eps for every \eps>0.
