{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:41Z","timestamp":1740109421908,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T00:00:00Z","timestamp":1559174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T00:00:00Z","timestamp":1559174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00224-019-09927-x","type":"journal-article","created":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T03:02:47Z","timestamp":1559185367000},"page":"199-226","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["New Bounds for Truthful Scheduling on Two Unrelated Selfish Machines"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8460-7296","authenticated-orcid":false,"given":"Olga","family":"Kuryatnikova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan C.","family":"Vera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,30]]},"reference":[{"issue":"3","key":"9927_CR1","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s00224-015-9625-5","volume":"57","author":"V Auletta","year":"2015","unstructured":"Auletta, V., Christodoulou, G., Penna, P.: Mechanisms for scheduling with single-bit private values. Theory Comput. Syst. 57(3), 523\u2013548 (2015)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9927_CR2","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s10107-016-1068-5","volume":"163","author":"Y Azar","year":"2017","unstructured":"Azar, Y., Hoefer, M., Maor, I., Reiffenh\u00e4user, R., V\u00f6cking, B.: Truthful mechanism design via correlated tree rounding. Math. Program. 163(1), 445\u2013469 (2017)","journal-title":"Math. Program."},{"issue":"3","key":"9927_CR3","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1007\/s00224-014-9601-5","volume":"57","author":"X Chen","year":"2015","unstructured":"Chen, X., Du, D., Zuluaga, L.: Copula-based randomized mechanisms for truthful scheduling on two unrelated machines. Theory Comput. Syst. 57(3), 753\u2013781 (2015)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"9927_CR4","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)","journal-title":"Algorithmica"},{"issue":"2","key":"9927_CR5","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1007\/s10107-015-0879-0","volume":"151","author":"C Dobre","year":"2015","unstructured":"Dobre, C., Vera, J.: Exploiting symmetry in copositive programs via semidefinite hierarchies. Math. Program. 151(2), 659\u2013680 (2015)","journal-title":"Math. Program."},{"key":"9927_CR6","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Sundararajan, M.: On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In: Proceedings of the 9th ACM Conference on Electronic Commerce EC \u201908, pp. 38\u201347 (2008)","DOI":"10.1145\/1386790.1386798"},{"issue":"4","key":"9927_CR7","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00224-016-9704-2","volume":"59","author":"K Elbassioni","year":"2016","unstructured":"Elbassioni, K., Mehlhorn, K., Ramezani, F.: Towards more practical linear programming-based techniques for algorithmic mechanism design. Theory Comput. Syst. 59(4), 641\u2013663 (2016)","journal-title":"Theory Comput. Syst."},{"key":"9927_CR8","unstructured":"Eustaquio, R.G., Karas, E.W., Ribeiro, A.A.: Constraint qualifications for nonlinear programming. In: Conference Proceedings. \nhttp:\/\/paginapessoal.utfpr.edu.br\/eustaquio\/my-research-interests\/kkterabio.pdf\n\n (2008)"},{"issue":"1","key":"9927_CR9","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.jpaa.2003.12.011","volume":"192","author":"K Gatermann","year":"2004","unstructured":"Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192(1), 95\u2013128 (2004)","journal-title":"J. Pure Appl. Algebra"},{"key":"9927_CR10","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"PC Gilmore","year":"1961","unstructured":"Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Oper. Res. 9, 849\u2013859 (1961)","journal-title":"Oper. Res."},{"issue":"3","key":"9927_CR11","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00453-007-9016-7","volume":"49","author":"L Gual\u00e0","year":"2007","unstructured":"Gual\u00e0, L., Proietti, G.: Exact and approximate truthful mechanisms for the shortest paths tree problem. Algorithmica 49(3), 171\u2013191 (2007)","journal-title":"Algorithmica"},{"key":"9927_CR12","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0108053","volume":"8","author":"JEK Jr.","year":"1960","unstructured":"Jr., J.E.K.: The cutting-plane method for solving convex programs. SIAM J. Appl. Math. 8, 703\u2013712 (1960)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"9927_CR13","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s10107-006-0039-7","volume":"109","author":"E de Klerk","year":"2007","unstructured":"de Klerk, E., Pasechnik, D., Schrijver, A.: Reduction of symmetric semidefinite programs using the regular \u2217-representation. Math. Program. 109(2), 613\u2013624 (2007)","journal-title":"Math. Program."},{"key":"9927_CR14","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 + \u03d5 for truthful scheduling mechanisms. Algorithmica 66, 211\u2013223 (2013)","journal-title":"Algorithmica"},{"issue":"6","key":"9927_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2049697.2049699","volume":"58","author":"R Lavi","year":"2011","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. J. ACM 58(6), 1\u201325 (2011)","journal-title":"J. ACM"},{"key":"9927_CR16","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J Lenstra","year":"1990","unstructured":"Lenstra, J., Shmoys, D., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990)","journal-title":"Math. Program."},{"key":"9927_CR17","unstructured":"Lu, P.: On 2-player randomized mechanisms for scheduling. In: Internet and Network Economics: 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings, pp. 30\u201341 (2009)"},{"key":"9927_CR18","doi-asserted-by":"crossref","unstructured":"Lu, P., Yu, C.: An improved randomized truthful mechanism for scheduling unrelated machines. In: Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008 Bordeaux : France (2008)","DOI":"10.1007\/978-3-540-92185-1_46"},{"key":"9927_CR19","first-page":"402","volume-title":"Lecture Notes in Computer Science","author":"Pinyan Lu","year":"2008","unstructured":"Lu, P., Yu, C.: Randomized truthful mechanisms for scheduling unrelated machines. In: Internet and Network Economics: 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings pp. 402\u2013413 (2008)"},{"key":"9927_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"9927_CR21","unstructured":"Mu\u2019alem, A., Schapira, M.: Setting lower bounds on truthfulness: Extended abstract. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms SODA \u201907, pp. 1143\u20131152 (2007)"},{"key":"9927_CR22","volume-title":"An introduction to Copulas","author":"R Nelsen","year":"2006","unstructured":"Nelsen, R.: An introduction to Copulas. Springer, New York (2006)"},{"issue":"1","key":"9927_CR23","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 Econom. Behav. 35(1), 166\u2013196 (2001)","journal-title":"Games Econom. Behav."},{"issue":"2","key":"9927_CR24","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0166-218X(85)90009-5","volume":"10","author":"C Potts","year":"1985","unstructured":"Potts, C.: Analysis of a linear programming heuristic for scheduling unrelated parallel machines. Discrete Appl. Math 10(2), 155\u2013164 (1985)","journal-title":"Discrete Appl. Math"},{"key":"9927_CR25","doi-asserted-by":"crossref","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)","DOI":"10.1145\/1064009.1064040"},{"issue":"2","key":"9927_CR26","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.orl.2004.05.004","volume":"33","author":"EV Shchepin","year":"2005","unstructured":"Shchepin, E.V., Vakhania, N.: An optimal rounding gives a better approximation for scheduling unrelated machines. Oper. Res. Lett. 33(2), 127\u2013133 (2005)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"9927_CR27","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/3040230.3040232","volume":"44","author":"R Vaze","year":"2017","unstructured":"Vaze, R., Coupechoux, M.: Online budgeted truthful matching. SIGMETRICS Perform. Eval. Rev. 44(3), 3\u20136 (2017)","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"9927_CR28","unstructured":"Wolfram|Alpha: \nhttp:\/\/www.wolframalpha.com\n\n (2009)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09927-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09927-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09927-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T19:05:25Z","timestamp":1590692725000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09927-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,30]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["9927"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09927-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2019,5,30]]},"assertion":[{"value":"30 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}