SIAM Journal on Computing · 2011 · 32 citations · 7 references
ComputingComputer ScienceAlgorithmsSchedulingTheory Of ComputationAlgorithm AnalysisApproximation AlgorithmsMachine SchedulingRandomized ComputationAlgorithmic Mechanism DesignApproximation SchemesMin-max SchedulingPolynomial Time ComplexityPolynomial-time AlgorithmsPolynomial-time Approximation SchemeRandomized Approximation AlgorithmsScheduling Approximation
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.
7
Roger B. Myerson · Mathematics of Operations Research · 1981 · 6.1K citations
Theodore Groves · Econometrica · 1973 · 3.3K citations
Management, Organization Studies, Organizational Behavior +17
Multipart pricing of public goods
Edward H. Clarke · Public Choice · 1971 · 3.3K citations
Noam Nisan, Amir Ronen · Games and Economic Behavior · 2001 · 1.4K citations