A truthful constant approximation for maximizing the minimum load on related machines

作者：Christodoulou George; Kovacs Annamaria; van Steec Rob^*

来源：Theoretical Computer Science, 2013, 489: 88-98.

DOI：10.1016/j.tcs.2013.04.003

• Algorithmic mechanism design
• Scheduling
• Machine covering
• Approximation algorithms

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. %26lt;br%26gt;We provide the first constant factor approximation for deterministic truthful mechanisms. In particular we come up with an approximation guarantee of 2 + epsilon, significantly improving on the previous upper bound of min(m, (2 + epsilon)s(m)/s(1)).

• 出版日期2013-6-10