A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines

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 approxi\-mation for deterministic truthful mechanisms. In particular we come up with a $2+\eps$ approximation guarantee, significantly improving on the previous upper bound of $\min(m,(2+\eps)s_m/s_1)$