{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:19Z","timestamp":1787340319509,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/080744992","type":"journal-article","created":{"date-parts":[[2011,6,24]],"date-time":"2011-06-24T12:43:30Z","timestamp":1308919410000},"page":"915-933","source":"Crossref","is-referenced-by-count":25,"title":["Truthful Approximation Schemes for Single-Parameter Agents"],"prefix":"10.1137","volume":"40","author":[{"given":"Peerapong","family":"Dhangwatnotai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shahar","family":"Dobzinski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shaddin","family":"Dughmi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,6,23]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.050"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1316-9"},{"key":"R3","unstructured":"A. Archer,\n                      Mechanisms for Discrete Optimization with Rational Agents\n                      , Ph.D. thesis, Cornell University, Ithaca, NY, 2004."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Archer and \u00c9. Tardos,\n                      Truthful mechanisms for one-parameter agents\n                      , in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2001, pp. 482\u2013491.","DOI":"10.1109\/SFCS.2001.959924"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"V. Auletta, R. De Prisco, P. Penna, and G. Persiano,\n                      Deterministic truthful approximation mechanisms for scheduling related machines\n                      , in Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Comput. Sci. 2996, Springer-Verlag, Berlin, New York, 2004, pp. 608\u2013619.","DOI":"10.1007\/978-3-540-24749-4_53"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Y. Azar and L. Epstein,\n                      Approximation schemes for covering and scheduling on related machines\n                      , in Proceedings of the First International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Comput. Sci. 1444, Springer-Verlag, Berlin, New York, 1998, pp. 39\u201347.","DOI":"10.1007\/BFb0053962"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"D. Buchfuhrer, S. Dughmi, H. Fu, R. Kleinberg, E. Mossel, C. Papadimitriou, M. Schapira, Y. Singer, and C. Umans,\n                      Inapproximability for VCG-based combinatorial auctions\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2010, pp. 518\u2013536.","DOI":"10.1137\/1.9781611973075.45"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"G. Christodoulou and A. Kov\u00e1cs,\n                      A deterministic truthful PTAS for scheduling related machines\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2010, pp. 1005\u20131016.","DOI":"10.1137\/1.9781611973075.81"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"S. Dughmi and T. Roughgarden,\n                      Black-box randomized reductions in algorithmic mechanism design\n                      , in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2010, pp. 775\u2013784.","DOI":"10.1109\/FOCS.2010.79"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1077-7"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"L. Epstein and R. van Stee,\n                      Maximizing the minimum load for selfish agents\n                      , in Proceedings of the 8th Conference on Latin American Theoretical Informatics (LATIN), Lecture Notes in Comput. Sci. 4957, Springer-Verlag, Berlin, New York, 2008, pp. 264\u2013275.","DOI":"10.1007\/978-3-540-78773-0_23"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"J. D. Hartline and B. Lucier,\n                      Bayesian algorithmic mechanism design\n                      , in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2010, pp. 301\u2013310.","DOI":"10.1145\/1806689.1806732"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0217033"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Kov\u00e1cs,\n                      Fast monotone 3-approximation algorithm for scheduling related machines\n                      , in Proceedings of the 13th Annual European Symposium on Algorithms (ESA), Lecture Notes in Comput. Sci. 3669, Springer-Verlag, Berlin, New York, 2005, pp. 616\u2013627.","DOI":"10.1007\/11561071_55"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. Kov\u00e1cs,\n                      Tighter approximation bounds for LPT scheduling in two special cases\n                      , in Proceedings of the 6th Italian Conference on Algorithms and Complexity (CIAC), Lecture Notes in Comput. Sci. 3998, Springer-Verlag, Berlin, New York, 2006, pp. 187\u2013198.","DOI":"10.1007\/11758471_20"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"R. Lavi,\n                      Computationally efficient approximation mechanisms\n                      , in Algorithmic Game Theory, N. Nisan, T. Roughgarden, \u00c9. Tardos, and V. Vazirani, eds., Cambridge University Press, Cambridge, UK, 2007, pp. 301\u2013329.","DOI":"10.1017\/CBO9780511800481.014"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. Lavi, A. Mu'alem, and N. Nisan,\n                      Towards a characterization of truthful combinatorial auctions\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscatway, NJ, 2003, pp. 574\u2013583.","DOI":"10.1109\/SFCS.2003.1238230"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"N. Nisan,\n                      Introduction to mechanism design (for computer scientists)\n                      , in Algorithmic Game Theory, N. Nisan, T. Roughgarden, \u00c9. Tardos, and V. Vazirani, eds., Cambridge University Press, Cambridge, UK, 2007, pp. 209\u2013241.","DOI":"10.1017\/CBO9780511800481.011"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou, M. Schapira, and Y. Singer,\n                      On the hardness of being truthful\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscatway, NJ, 2008, pp. 250\u2013259.","DOI":"10.1109\/FOCS.2008.54"},{"key":"R24","unstructured":"D. Parkes,\n                      Iterative Combinatorial Auctions: Achieving Economic and Computational Efficiency\n                      , Ph.D. thesis, University of Pennsylvania, Philadelphia, 2001."},{"key":"R25","first-page":"381","volume":"71","author":"Riley J.","year":"1981","journal-title":"Amer. Econom. Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-8282","issn-type":"print"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080744992","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:51Z","timestamp":1787336991000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080744992"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/080744992"],"URL":"https:\/\/doi.org\/10.1137\/080744992","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}