Truthful Approximation Schemes for Single-Parameter Agents

Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden

SIAM Journal on Computing · 2011 · 32 citations · 7 references

Concepts

Abstract

We present the first monotone randomized polynomial-time approximation scheme (PTAS) for minimizing the makespan of parallel related machines ($Q||C_{\max}$), the paradigmatic problem in single-parameter algorithmic mechanism design. This result immediately gives a polynomial-time, truthful (in expectation) mechanism whose approximation guarantee attains the best-possible one for all polynomial-time algorithms (assuming $P\neq NP$). Our algorithmic techniques are flexible and also yield a monotone deterministic quasi-PTAS for $Q||C_{\max}$ and a monotone randomized PTAS for max-min scheduling on related machines.

References

7