{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:48Z","timestamp":1725488988053},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_41","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"454-464","source":"Crossref","is-referenced-by-count":22,"title":["A Lower Bound of 1\u2009+\u2009\u03c6 for Truthful Scheduling Mechanisms"],"prefix":"10.1007","author":[{"given":"Elias","family":"Koutsoupias","sequence":"first","affiliation":[]},{"given":"Angelina","family":"Vidali","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"41_CR1","doi-asserted-by":"crossref","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. 69\u201382 (2005)","DOI":"10.1007\/978-3-540-31856-9_6"},{"key":"41_CR2","unstructured":"Archer, A.: Mechanisms for Discrete Optimization with Rational Agents. PhD thesis, Cornell University (January 2004)"},{"key":"41_CR3","first-page":"205","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"A. Archer","year":"2003","unstructured":"Archer, A., Papadimitriou, C.H., Talwar, K., Tardos, \u00c9.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 205\u2013214. ACM Press, New York (2003)"},{"key":"41_CR4","doi-asserted-by":"crossref","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)","DOI":"10.1109\/SFCS.2001.959924"},{"key":"41_CR5","unstructured":"Babaioff, M., Lavi, R., Pavlov, E.: Mechanism design for single-value domains. In: Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference (AAAI), pp. 241\u2013247 (2005)"},{"key":"41_CR6","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gonen, R., Nisan, N.: Incentive compatible multi unit combinatorial auctions. In: Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), pp. 72\u201387 (2003)","DOI":"10.1145\/846241.846250"},{"key":"41_CR7","first-page":"39","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC)","author":"P. Briest","year":"2005","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation techniques for utilitarian mechanism design. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 39\u201348. ACM Press, New York (2005)"},{"key":"41_CR8","first-page":"1163","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"G. Christodoulou","year":"2007","unstructured":"Christodoulou, G., Koutsoupias, E., Vidali, A.: A lower bound for scheduling mechanisms. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1163\u20131169. ACM Press, New York (2007)"},{"key":"41_CR9","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01726210","volume":"8","author":"E. Clarke","year":"1971","unstructured":"Clarke, E.: Multipart pricing of public goods. Public Choice\u00a08, 17\u201333 (1971)","journal-title":"Public Choice"},{"key":"41_CR10","first-page":"610","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC)","author":"S. Dobzinski","year":"2005","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 610\u2013618. ACM Press, New York (2005)"},{"key":"41_CR11","first-page":"644","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC)","author":"S. Dobzinski","year":"2006","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Truthful randomized mechanisms for combinatorial auctions. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 644\u2013652. ACM Press, New York (2006)"},{"key":"41_CR12","doi-asserted-by":"crossref","unstructured":"Christodoulou, E.K.G., Kovacs, A.: Mechanism design for fractional scheduling on unrelated machines. In: ICALP 2007 (to appear, 2007)","DOI":"10.1007\/978-3-540-73420-8_6"},{"key":"41_CR13","doi-asserted-by":"publisher","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econometrica\u00a041, 617\u2013631 (1973)","journal-title":"Econometrica"},{"key":"41_CR14","unstructured":"Gui, H., M\u00fcller, R., Vohra, R.V.: Dominant strategy mechanisms with multidimensional types. In: Computing and Markets (2005)"},{"key":"41_CR15","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 Publishing Co. Boston, MA, USA (1996)"},{"issue":"2","key":"41_CR16","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM\u00a023(2), 317\u2013327 (1976)","journal-title":"J. ACM"},{"key":"41_CR17","unstructured":"Kevin, R.: The characterization of implementable choice rules. Aggregation and Revelation of Preferences, 321\u2013348 (1979)"},{"key":"41_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1007\/11561071_55","volume-title":"Algorithms \u2013 ESA 2005","author":"A. Kovacs","year":"2005","unstructured":"Kovacs, A.: Fast monotone 3-approximation algorithm for scheduling related machines. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 616\u2013627. Springer, Heidelberg (2005)"},{"key":"41_CR19","doi-asserted-by":"crossref","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)","DOI":"10.1109\/SFCS.2003.1238230"},{"key":"41_CR20","volume-title":"Proceedings 8th 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: Proceedings 8th ACM Conference on Electronic Commerce (EC), ACM Press, New York (2007)"},{"issue":"1","key":"41_CR21","doi-asserted-by":"publisher","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. Mathematical Programming\u00a046(1), 259\u2013271 (1990)","journal-title":"Mathematical Programming"},{"key":"41_CR22","first-page":"1143","volume-title":"Proceedings of the Eighteenth 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 Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1143\u20131152. ACM Press, New York (2007)"},{"key":"41_CR23","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1145\/301250.301287","volume-title":"Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC)","author":"N. Nisan","year":"1999","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design (extended abstract). In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC), pp. 129\u2013140. ACM Press, New York (1999)"},{"key":"41_CR24","doi-asserted-by":"publisher","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 and Economic Behavior\u00a035, 166\u2013196 (2001)","journal-title":"Games and Economic Behavior"},{"key":"41_CR25","doi-asserted-by":"publisher","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. ACM Press, New York (2005)"},{"key":"41_CR26","doi-asserted-by":"publisher","first-page":"8","DOI":"10.2307\/2977633","volume":"16","author":"W. Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculations, auctions and competitive sealed tenders. Journal of Finance\u00a016, 8\u201337 (1961)","journal-title":"Journal of Finance"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:29:08Z","timestamp":1619519348000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}