Truthful Approximation Schemes for Single-Parameter Agents

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 not equal to NP). Our algorithmic techniques are flexible and also yield, among other results, a monotone deterministic quasi-PTAS for Q||C max and a monotone randomized PTAS for max-min scheduling on related machines.

Authors

• Peerapong Dhangwatnotai
• Shahar Dobzinski
• Shaddin Dughmi
• Tim Roughgarden

Keywords

• Computer science
• Polynomials
• Approximation algorithms
• Algorithm design and analysis
• Scheduling algorithm
• Peer to peer computing
• Resource management
• Costs
• Engineering profession
• Application software
• Estimation Strategy
• Deterministic
• Algorithm Design
• Mechanical Design
• Polynomial-time Algorithm
• Algorithmic Techniques
• Related Problems
• Data Privacy
• Estimation Algorithm
• Integrable
• Implementation Of Algorithm
• Amount Of Work
• Generation Algorithm
• Nondecreasing
• Legality
• Validation Parameters
• Probability 1
• Compact Representation
• Approximate Ratio
• Power-of-two
• Job Scheduling
• Potential Endpoints
• Optimal Partition
• Exact Optimization
• Minimum Load
• Algorithmic Mechanism Design
• Single Parameter Agents
• Monotone Algorithms
• Scheduling