{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:42Z","timestamp":1740109302072,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T00:00:00Z","timestamp":1624406400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T00:00:00Z","timestamp":1624406400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001871","name":"Funda para a Ciia e a Tecnologia","doi-asserted-by":"publisher","award":["Alexander von Humboldt-Stiftung"],"award-info":[{"award-number":["Alexander von Humboldt-Stiftung"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s00453-021-00847-2","type":"journal-article","created":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T16:02:31Z","timestamp":1624464151000},"page":"2895-2913","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A New Lower Bound for Deterministic Truthful Scheduling"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2382-1779","authenticated-orcid":false,"given":"Yiannis","family":"Giannakopoulos","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Hammerl","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5474-3614","authenticated-orcid":false,"given":"Diogo","family":"Po\u00e7as","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,23]]},"reference":[{"issue":"2","key":"847_CR1","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1287\/moor.1110.0534","volume":"37","author":"I Ashlagi","year":"2012","unstructured":"Ashlagi, I., Dobzinski, S., Lavi, R.: Optimal lower bounds for anonymous scheduling mechanisms. Math. Oper. Res. 37(2), 244\u2013258 (2012). https:\/\/doi.org\/10.1287\/moor.1110.0534","journal-title":"Math. Oper. Res."},{"issue":"3","key":"847_CR2","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.jcss.2008.10.001","volume":"75","author":"V Auletta","year":"2009","unstructured":"Auletta, V., De Prisco, R., Penna, P., Persiano, G.: The power of verification for one-parameter agents. J. Comput. Syst. Sci. 75(3), 190\u2013211 (2009). https:\/\/doi.org\/10.1016\/j.jcss.2008.10.001","journal-title":"J. Comput. Syst. Sci."},{"key":"847_CR3","doi-asserted-by":"publisher","unstructured":"Archer, A., Tardos, \u00c9.: Truthful mechanisms for one-parameter agents. In: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science (FOCS), pp. 482\u2013491, (2001). https:\/\/doi.org\/10.1109\/sfcs.2001.959924","DOI":"10.1109\/sfcs.2001.959924"},{"issue":"3","key":"847_CR4","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1007\/s00224-014-9601-5","volume":"57","author":"X Chen","year":"2015","unstructured":"Chen, X., Donglei, D., Zuluaga, L.F.: Copula-based randomized mechanisms for truthful scheduling on two unrelated machines. Theory Comput. Syst. 57(3), 753\u2013781 (2015). https:\/\/doi.org\/10.1007\/s00224-014-9601-5","journal-title":"Theory Comput. Syst."},{"key":"847_CR5","doi-asserted-by":"publisher","unstructured":"Chawla, S., Hartline, J.D., Malec, D., Sivan B.: Prior-independent mechanisms for scheduling. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pp. 51\u201360, (2013). https:\/\/doi.org\/10.1145\/2488608.2488616","DOI":"10.1145\/2488608.2488616"},{"issue":"4","key":"847_CR6","doi-asserted-by":"publisher","first-page":"1572","DOI":"10.1137\/120866038","volume":"42","author":"G Christodoulou","year":"2013","unstructured":"Christodoulou, G., Kov\u00e1cs, A.: A deterministic truthful PTAS for scheduling related machines. SIAM J. Comput. 42(4), 1572\u20131595 (2013). https:\/\/doi.org\/10.1137\/120866038","journal-title":"SIAM J. Comput."},{"issue":"2","key":"847_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1721837.1721854","volume":"6","author":"G Christodoulou","year":"2010","unstructured":"Christodoulou, G., Koutsoupias, E., Kov\u00e1cs, A.: Mechanism design for fractional scheduling on unrelated machines. ACM Trans. Algorithms 6(2), 1\u201318 (2010). https:\/\/doi.org\/10.1145\/1721837.1721854","journal-title":"ACM Trans. Algorithms"},{"key":"847_CR8","doi-asserted-by":"publisher","unstructured":"Christodoulou, G., Koutsoupias, E., Kov\u00e1cs A.: On the Nisan-Ronen conjecture for submodular valuations. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1086\u20131096, (2020). https:\/\/doi.org\/10.1145\/3357713.3384299","DOI":"10.1145\/3357713.3384299"},{"key":"847_CR9","unstructured":"Christodoulou, G., Koutsoupias, E., Kov\u00e1cs, A.: On the Nisan-Ronen conjecture. CoRR, abs\/2011.14434, 2020. [arXiv:2011.14434v3]"},{"key":"847_CR10","doi-asserted-by":"publisher","unstructured":"Christodoulou, G., Koutsoupias, E., Vidali, A.: A lower bound for scheduling mechanisms. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1163\u20131170, (2007). https:\/\/doi.org\/10.5555\/1283383.1283508","DOI":"10.5555\/1283383.1283508"},{"issue":"4","key":"847_CR11","doi-asserted-by":"publisher","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 lower bound for scheduling mechanisms. Algorithmica 55(4), 729\u2013740 (2009). https:\/\/doi.org\/10.1007\/s00453-008-9165-3","journal-title":"Algorithmica"},{"issue":"3","key":"847_CR12","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/080744992","journal-title":"SIAM J. Comput."},{"key":"847_CR13","unstructured":"Dobzinski, S., Shaulker, A.: Improved lower bounds for truthful scheduling. abs\/2007.04362, 2020. [arXiv:2007.04362v2]"},{"key":"847_CR14","doi-asserted-by":"publisher","unstructured":"Daskalakis, C., Weinberg, S.M.: Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. In: Proceedings of the 26th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1934\u20131952, (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.130","DOI":"10.1137\/1.9781611973730.130"},{"issue":"1","key":"847_CR15","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1287\/moor.2015.0730","volume":"41","author":"L Epstein","year":"2016","unstructured":"Epstein, L., Levin, A., Van Stee, R.: A unified approach to truthful scheduling on related machines. Math. Oper. Res. 41(1), 332\u2013351 (2016). https:\/\/doi.org\/10.1287\/moor.2015.0730","journal-title":"Math. Oper. Res."},{"key":"847_CR16","doi-asserted-by":"publisher","unstructured":"Filos-Ratsikas, A., Giannakopoulos, Y., Lazos, P.: The Pareto frontier of inefficiency in mechanism design. In: Proceedings of the 15th Conference on Web and Internet Economics (WINE). pp. 186\u2013199, (2019). https:\/\/doi.org\/10.1007\/978-3-030-35389-6_14","DOI":"10.1007\/978-3-030-35389-6_14"},{"key":"847_CR17","doi-asserted-by":"publisher","unstructured":"Giannakopoulos, Y., Hammerl, A., Po\u00e7as, D.: A new lower bound for deterministic truthful scheduling. In: Proceedings of the 13th symposium on algorithmic game theory (SAGT), (2020). https:\/\/doi.org\/10.1007\/978-3-030-57980-7_15","DOI":"10.1007\/978-3-030-57980-7_15"},{"issue":"4","key":"847_CR18","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/3105968","volume":"5","author":"Y Giannakopoulos","year":"2017","unstructured":"Giannakopoulos, Y., Kyropoulou, M.: The VCG mechanism for Bayesian scheduling. ACM Trans. Econ. Comput. 5(4), 19:1-19:16 (2017). https:\/\/doi.org\/10.1145\/3105968","journal-title":"ACM Trans. Econ. Comput."},{"key":"847_CR19","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.tcs.2019.01.022","volume":"778","author":"Y Giannakopoulos","year":"2019","unstructured":"Giannakopoulos, Y., Koutsoupias, E., Kyropoulou, M.: The anarchy of scheduling without money. Theor. Comput. Sci 778, 19\u201332 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2019.01.022","journal-title":"Theor. Comput. Sci"},{"key":"847_CR20","first-page":"1","volume-title":"Approximation Algorithms for NP-hard Problems","author":"LA Hall","year":"1997","unstructured":"Hall, L.A.: Approximation algorithms for scheduling. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-hard Problems, pp. 1\u201345. PWS Publishing Company, Boston (1997)"},{"issue":"3","key":"847_CR21","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00224-013-9473-0","volume":"54","author":"E Koutsoupias","year":"2014","unstructured":"Koutsoupias, E.: Scheduling without payments. Theory Comput. Syst. 54(3), 375\u2013387 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9473-0","journal-title":"Theory Comput. Syst."},{"key":"847_CR22","doi-asserted-by":"publisher","unstructured":"Koutsoupias, E., Vidali, A.: A lower bound of $$1+ \\phi$$ for truthful scheduling mechanisms. In: Proceedings of Mathematical Foundations of Computer Science (MFCS), pp. 454\u2013464, (2007). https:\/\/doi.org\/10.1007\/978-3-540-74456-6_41","DOI":"10.1007\/978-3-540-74456-6_41"},{"issue":"1","key":"847_CR23","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00453-012-9634-6","volume":"66","author":"E Koutsoupias","year":"2013","unstructured":"Koutsoupias, E., Vidali, A.: A lower bound of 1+$$\\phi$$ for truthful scheduling mechanisms. Algorithmica 66(1), 211\u2013223 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9634-6","journal-title":"Algorithmica"},{"issue":"2","key":"847_CR24","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s00224-019-09927-x","volume":"64","author":"O Kuryatnikova","year":"2019","unstructured":"Kuryatnikova, O., Vera, J.C.: New bounds for truthful scheduling on two unrelated selfish machines. Theory Comput. Syst. 64(2), 199\u2013226 (2019). https:\/\/doi.org\/10.1007\/s00224-019-09927-x","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"847_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.geb.2008.08.001","volume":"67","author":"R Lavi","year":"2009","unstructured":"Lavi, R., Swamy, C.: Truthful mechanism design for multidimensional scheduling via cycle monotonicity. Games Econ. Behav. 67(1), 99\u2013124 (2009). https:\/\/doi.org\/10.1016\/j.geb.2008.08.001","journal-title":"Games Econ. Behav."},{"issue":"1","key":"847_CR26","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/bf01585745","volume":"46","author":"JK 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). https:\/\/doi.org\/10.1007\/bf01585745","journal-title":"Math. Program."},{"key":"847_CR27","doi-asserted-by":"publisher","unstructured":"Lu P.: On 2-player randomized mechanisms for scheduling. In: Proceedings of the 5th international workshop on internet and network economics (WINE), pp. 30\u201341, (2009). https:\/\/doi.org\/10.1007\/978-3-642-10841-9_5","DOI":"10.1007\/978-3-642-10841-9_5"},{"key":"847_CR28","doi-asserted-by":"publisher","unstructured":"Lu, P., Yu, C.: An improved randomized truthful mechanism for scheduling unrelated machines. In: Proceedings of the 25th international symposium on theoretical aspects of computer science (STACS), pp. 527\u2013538, (2008). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2008.1314","DOI":"10.4230\/LIPIcs.STACS.2008.1314"},{"key":"847_CR29","doi-asserted-by":"publisher","unstructured":"Lu, P., Yu, C.: Randomized truthful mechanisms for scheduling unrelated machines. In: Proceedings of the 4th International Workshop on Internet and Network Economics (WINE), pp. 402\u2013413, (2008). https:\/\/doi.org\/10.1007\/978-3-540-92185-1_46","DOI":"10.1007\/978-3-540-92185-1_46"},{"key":"847_CR30","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.geb.2018.02.001","volume":"110","author":"A Mualem","year":"2018","unstructured":"Mu'alem, A., Schapira, M.: Setting lower bounds on truthfulness. Games Econ. Behav. 110, 174\u2013193 (2018). https:\/\/doi.org\/10.1016\/j.geb.2018.02.001","journal-title":"Games Econ. Behav."},{"key":"847_CR31","doi-asserted-by":"publisher","unstructured":"Nisan, N.: Introduction to mechanism design (for computer scientists). In: Nisan, N., Roughgarden, T., Tardos, \u00c9., Vazirani, V. (eds.) Algorithmic Game Theory, chapter 9. Cambridge University Press, Cambridge (2007). https:\/\/doi.org\/10.1017\/cbo9780511800481.011","DOI":"10.1017\/cbo9780511800481.011"},{"key":"847_CR32","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design (extended abstract). In: The 31st Annual ACM symposium on Theory of Computing (STOC), pp. 129\u2013140, (1999)","DOI":"10.1145\/301250.301287"},{"issue":"1\/2","key":"847_CR33","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 Econ. Behav. 35(1\/2), 166\u2013196 (2001). https:\/\/doi.org\/10.1006\/game.1999.0790","journal-title":"Games Econ. Behav."},{"key":"847_CR34","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/j.geb.2012.09.002","volume":"86","author":"P Penna","year":"2014","unstructured":"Penna, P., Ventre, C.: Optimal collusion-resistant mechanisms with verification. Games Econ. Behav. 86, 491\u2013509 (2014). https:\/\/doi.org\/10.1016\/j.geb.2012.09.002","journal-title":"Games Econ. Behav."},{"key":"847_CR35","doi-asserted-by":"publisher","unstructured":"Saks M., Yu, L.: Weak monotonicity suffices for truthfulness on convex domains. In: Proceedings of the 6th ACM Conference on Electronic Commerce (EC), pp. 286\u2013293, (2005). https:\/\/doi.org\/10.1145\/1064009.1064040","DOI":"10.1145\/1064009.1064040"},{"key":"847_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2003","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2003). https:\/\/doi.org\/10.1007\/978-3-662-04565-7"},{"key":"847_CR37","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.tcs.2013.07.034","volume":"518","author":"C Ventre","year":"2014","unstructured":"Ventre, C.: Truthful optimization using mechanisms with verification. Theor. Comput. Sci. 518, 64\u201379 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2013.07.034","journal-title":"Theor. Comput. Sci."},{"issue":"21\u201323","key":"847_CR38","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.tcs.2009.02.001","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00847-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00847-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00847-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T11:06:25Z","timestamp":1628161585000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00847-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,23]]},"references-count":38,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["847"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00847-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,6,23]]},"assertion":[{"value":"14 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}