hide
Free keywords:
-
Abstract:
Designing truthful mechanisms for scheduling on related machines is a very
important problem in single-parameter mechanism design. We consider the
covering objective, that is we are
interested in maximizing the minimum completion time of a
machine. This problem falls into the class of problems where the
optimal allocation can be truthfully implemented. A major open issue for
this class is whether truthfulness affects the polynomial-time implementation.
We provide the first
constant factor approximation for deterministic truthful mechanisms.
In particular we come up with a approximation guarantee of 2+\eps,
significantly improving on the previous upper bound of
\min(m,(2+\eps)s_m/s_1).
