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 approximation for deterministic truthful mechanisms. In particular we come up with an approximation guarantee of 2+ε, significantly improving on the previous upper bound of min(m,(2+ε)sm/s1).