{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:36:27Z","timestamp":1770896187797,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,3,6]],"date-time":"2012-03-06T00:00:00Z","timestamp":1330992000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00453-012-9634-6","type":"journal-article","created":{"date-parts":[[2012,3,6]],"date-time":"2012-03-06T01:07:27Z","timestamp":1330996047000},"page":"211-223","source":"Crossref","is-referenced-by-count":30,"title":["A Lower Bound of 1+\u03c6 for Truthful Scheduling Mechanisms"],"prefix":"10.1007","volume":"66","author":[{"given":"Elias","family":"Koutsoupias","sequence":"first","affiliation":[]},{"given":"Angelina","family":"Vidali","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,3,6]]},"reference":[{"key":"9634_CR1","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"D.S. Hochbaum","year":"1996","unstructured":"Hochbaum, D.S.: Approximation Algorithms for NP-Hard Problems. PWS, Boston (1996)"},{"issue":"1","key":"9634_CR2","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1), 259\u2013271 (1990)","journal-title":"Math. Program."},{"issue":"2","key":"9634_CR3","first-page":"317","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J.\u00a0ACM 23(2), 317\u2013327 (1976). doi: 10.1145\/321941.321951","journal-title":"J.\u00a0ACM"},{"key":"9634_CR4","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1006\/game.1999.0790","volume":"35","author":"N. Nisan","year":"2001","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35, 166\u2013196 (2001)","journal-title":"Games Econ. Behav."},{"key":"9634_CR5","first-page":"454","volume-title":"MFCS","author":"E. Koutsoupias","year":"2007","unstructured":"Koutsoupias, E., Vidali, A.: A lower bound of 1+\u03d5 for truthful scheduling mechanisms. In: MFCS, pp. 454\u2013464 (2007)"},{"key":"9634_CR6","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/1386790.1386798","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"S. Dobzinski","year":"2008","unstructured":"Dobzinski, S., Sundararajan, M.: On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In: ACM Conference on Electronic Commerce (EC), pp. 38\u201347 (2008)"},{"key":"9634_CR7","first-page":"297","volume-title":"Algorithms\u2014ESA, 16th Annual European Symposium","author":"G. Christodoulou","year":"2008","unstructured":"Christodoulou, G., Koutsoupias, E., Vidali, A.: A characterization of 2-player mechanisms for scheduling. In: Algorithms\u2014ESA, 16th Annual European Symposium, pp. 297\u2013307 (2008)"},{"key":"9634_CR8","first-page":"1143","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"A. Mu\u2019alem","year":"2007","unstructured":"Mu\u2019alem, A., Schapira, M.: Setting lower bounds on truthfulness. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1143\u20131152 (2007)"},{"issue":"4","key":"9634_CR9","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s00453-008-9165-3","volume":"55","author":"G. Christodoulou","year":"2009","unstructured":"Christodoulou, G., Koutsoupias, E., Vidali, A.: A characterization of 2-player mechanisms for scheduling. Algorithmica 55(4), 729\u2013740 (2009)","journal-title":"Algorithmica"},{"key":"9634_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/1566374.1566399","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"I. Ashlagi","year":"2009","unstructured":"Ashlagi, I., Dobzinski, S., Lavi, R.: An optimal lower bound for anonymous scheduling mechanisms. In: ACM Conference on Electronic Commerce (EC), pp. 169\u2013176 (2009)"},{"key":"9634_CR11","first-page":"527","volume-title":"STACS, 25th Annual Symposium on Theoretical Aspects of Computer Science","author":"P. Lu","year":"2008","unstructured":"Lu, P., Yu, C.: An improved randomized truthful mechanism for scheduling unrelated machines. In: STACS, 25th Annual Symposium on Theoretical Aspects of Computer Science, pp. 527\u2013538 (2008)"},{"key":"9634_CR12","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/978-3-540-92185-1_46","volume-title":"Internet and Network Economics, 4th International Workshop (WINE)","author":"P. Lu","year":"2008","unstructured":"Lu, P., Yu, C.: Randomized truthful mechanisms for scheduling unrelated machines. In: Internet and Network Economics, 4th International Workshop (WINE), pp. 402\u2013413 (2008)"},{"key":"9634_CR13","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Koutsoupias, E., Kov\u00e1cs, A.: Mechanism design for fractional scheduling on unrelated machines. ACM Trans. Algorithms 6(2) (2010)","DOI":"10.1145\/1721837.1721854"},{"key":"9634_CR14","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1145\/1807342.1807368","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"E. Cohen","year":"2010","unstructured":"Cohen, E., Feldman, M., Fiat, A., Kaplan, H., Olonetsky, S.: Envy-free makespan approximation: extended abstract. In: ACM Conference on Electronic Commerce (EC), pp. 159\u2013166 (2010)"},{"key":"9634_CR15","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/978-3-642-04428-1_11","volume-title":"Algorithmic Decision Theory, 1st International Conference (ADT)","author":"A. Mu\u2019alem","year":"2009","unstructured":"Mu\u2019alem, A.: On multi-dimensional envy-free mechanisms. In: Algorithmic Decision Theory, 1st International Conference (ADT), pp. 120\u2013131 (2009)"},{"key":"9634_CR16","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-642-25510-6_8","volume-title":"Internet and Network Economics, 7th International Workshop (WINE)","author":"G. Christodoulou","year":"2011","unstructured":"Christodoulou, G., Kov\u00e1cs, A.: A global characterization of envy-free truthful scheduling of two tasks. In: Internet and Network Economics, 7th International Workshop (WINE), pp. 84\u201396 (2011)"},{"key":"9634_CR17","first-page":"252","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"R. Lavi","year":"2007","unstructured":"Lavi, R., Swamy, C.: Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity. In: ACM Conference on Electronic Commerce (EC), pp. 252\u2013261 (2007)"},{"issue":"21\u201323","key":"9634_CR18","doi-asserted-by":"crossref","first-page":"2196","DOI":"10.1016\/j.tcs.2009.02.001","volume":"410","author":"C. Yu","year":"2009","unstructured":"Yu, C.: Truthful mechanisms for two-range-values variant of unrelated scheduling. Theor. Comput. Sci. 410(21\u201323), 2196\u20132206 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9634_CR19","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1287\/moor.6.1.58","volume":"6","author":"R.B. Myerson","year":"1981","unstructured":"Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58\u201373 (1981)","journal-title":"Math. Oper. Res."},{"key":"9634_CR20","first-page":"482","volume-title":"42nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"A. Archer","year":"2001","unstructured":"Archer, A., Tardos, \u00c9.: Truthful mechanisms for one-parameter agents. In: 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 482\u2013491 (2001)"},{"key":"9634_CR21","unstructured":"Archer, A.: Mechanisms for discrete optimization with rational agents. PhD thesis, Cornell University (January 2004)"},{"issue":"3","key":"9634_CR22","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1137\/080744992","volume":"40","author":"P. Dhangwatnotai","year":"2011","unstructured":"Dhangwatnotai, P., Dobzinski, S., Dughmi, S., Roughgarden, T.: Truthful approximation schemes for single-parameter agents. SIAM J. Comput. 40(3), 915\u2013933 (2011)","journal-title":"SIAM J. Comput."},{"key":"9634_CR23","series-title":"LNCS","first-page":"608","volume-title":"21st Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"V. Auletta","year":"2004","unstructured":"Auletta, V., Prisco, R.D., Penna, P., Persiano, G.: Deterministic truthful approximation mechanisms for scheduling related machines. In: 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS). LNCS, vol.\u00a02996, pp. 608\u2013619 (2004)"},{"key":"9634_CR24","first-page":"69","volume-title":"22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"N. Andelman","year":"2005","unstructured":"Andelman, N., Azar, Y., Sorani, M.: Truthful approximation mechanisms for scheduling selfish related machines. In: 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp.\u00a069\u201382 (2005)"},{"key":"9634_CR25","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1007\/11561071_55","volume-title":"Algorithms\u2014ESA 2005: 13th Annual European Symposium","author":"A. Kov\u00e1cs","year":"2005","unstructured":"Kov\u00e1cs, A.: Fast monotone 3-approximation algorithm for scheduling related machines. In: Algorithms\u2014ESA 2005: 13th Annual European Symposium, pp. 616\u2013627 (2005)"},{"key":"9634_CR26","unstructured":"Kov\u00e1cs, A.: Fast algorithms for two scheduling problems. PhD thesis, Universit\u00e4t des Saarlandes (2007)"},{"key":"9634_CR27","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1137\/1.9781611973075.81","volume-title":"21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"G. Christodoulou","year":"2010","unstructured":"Christodoulou, G., Kov\u00e1cs, A.: A deterministic truthful PTAS for scheduling related machines. In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1005\u20131016 (2010)"},{"key":"9634_CR28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N. Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)"},{"key":"9634_CR29","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1007\/978-3-642-25510-6_36","volume-title":"Internet and Network Economics\u20147th International Workshop (WINE)","author":"A. Vidali","year":"2011","unstructured":"Vidali, A.: Extending characterizations of truthful mechanisms from subdomains to domains. In: Internet and Network Economics\u20147th International Workshop (WINE), pp. 408\u2013414 (2011)"},{"key":"9634_CR30","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1145\/1064009.1064040","volume-title":"Proceedings 6th ACM Conference on Electronic Commerce (EC)","author":"M.E. Saks","year":"2005","unstructured":"Saks, M.E., Yu, L.: Weak monotonicity suffices for truthfulness on convex domains. In: Proceedings 6th ACM Conference on Electronic Commerce (EC), pp. 286\u2013293 (2005)"},{"key":"9634_CR31","series-title":"Dagstuhl Seminar Proceedings","volume-title":"Computing and Markets","author":"H. Gui","year":"2005","unstructured":"Gui, H., M\u00fcller, R., Vohra, R.V.: Dominant strategy mechanisms with multidimensional types. In: Computing and Markets. Dagstuhl Seminar Proceedings (2005)"},{"key":"9634_CR32","first-page":"574","volume-title":"44th Symposium on Foundations of Computer Science (FOCS)","author":"R. Lavi","year":"2003","unstructured":"Lavi, R., Mu\u2019alem, A., Nisan, N.: Towards a characterization of truthful combinatorial auctions. In: 44th Symposium on Foundations of Computer Science (FOCS), pp. 574\u2013583 (2003)"},{"key":"9634_CR33","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1145\/1386790.1386799","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"D. Monderer","year":"2008","unstructured":"Monderer, D.: Monotonicity and implementability. In: ACM Conference on Electronic Commerce (EC), p. 48 (2008)"},{"key":"9634_CR34","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/1386790.1386796","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"A. Archer","year":"2008","unstructured":"Archer, A., Kleinberg, R.: Truthful germs are contagious: a\u00a0local to global characterization of truthfulness. In: ACM Conference on Electronic Commerce (EC), pp. 21\u201330 (2008)"},{"key":"9634_CR35","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1007\/978-3-642-10841-9_31","volume-title":"Internet and Network Economics, 5th International Workshop (WINE)","author":"A. Vidali","year":"2009","unstructured":"Vidali, A.: The geometry of truthfulness. In: Internet and Network Economics, 5th International Workshop (WINE), pp. 340\u2013350 (2009)"},{"key":"9634_CR36","unstructured":"Kevin, R.: The characterization of implementable choice rules. Aggreg. Revel. Prefer. 321\u2013348 (1979)"},{"key":"9634_CR37","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W. Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculations, auctions and competitive sealed tenders. J. Finance 16, 8\u201337 (1961)","journal-title":"J. Finance"},{"key":"9634_CR38","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01726210","volume":"8","author":"E. Clarke","year":"1971","unstructured":"Clarke, E.: Multipart pricing of public goods. Public Choice 8, 17\u201333 (1971)","journal-title":"Public Choice"},{"key":"9634_CR39","doi-asserted-by":"crossref","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econometrica 41, 617\u2013631 (1973)","journal-title":"Econometrica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9634-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9634-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9634-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T12:48:27Z","timestamp":1641041307000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9634-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,6]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9634"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9634-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,6]]}}}