{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T00:07:49Z","timestamp":1773965269843,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662447765","type":"print"},{"value":"9783662447772","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44777-2_2","type":"book-chapter","created":{"date-parts":[[2014,8,16]],"date-time":"2014-08-16T06:43:15Z","timestamp":1408171395000},"page":"13-24","source":"Crossref","is-referenced-by-count":17,"title":["Optimal Coordination Mechanisms for Multi-job Scheduling Games"],"prefix":"10.1007","author":[{"given":"Fidaa","family":"Abed","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 R.","family":"Correa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chien-Chung","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/978-3-642-33090-2_3","volume-title":"Algorithms \u2013 ESA 2012","author":"F. Abed","year":"2012","unstructured":"Abed, F., Huang, C.-C.: Preemptive coordination mechanisms for unrelated machines. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 12\u201323. Springer, Heidelberg (2012)"},{"key":"2_CR2","unstructured":"Azar, Y., Jain, K., Mirrokni, V.S. (Almost) Optimal coordination mechanisms for unrelated machine scheduling. In: SODA (2008)"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Bhattacharyay, S., Imz, S., Kulkarnix, J., Munagala, K.: Coordination mechanisms from (almost) all scheduling policies. In: ITCS (2014)","DOI":"10.1145\/2554797.2554811"},{"issue":"5","key":"2_CR4","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/j.orl.2005.08.003","volume":"34","author":"T. Brueggemann","year":"2006","unstructured":"Brueggemann, T., Hurink, J.L., Kern, W.: Quality of move-optimal schedules for minimizing total weighted completion time. Oper. Res. Lett.\u00a034(5), 583\u2013590 (2006)","journal-title":"Oper. Res. Lett."},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J. Bruno","year":"1974","unstructured":"Bruno, J., Coffman, E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Commun. ACM\u00a017, 382\u2013387 (1974)","journal-title":"Commun. ACM"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Caragiannis, I.: Efficient coordination mechanisms for unrelated machine scheduling. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.89"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Chen, B., Potts, C.N., Woeginger, G.J.: A review of machine scheduling: Complexity, algorithms and approximability. In: Handbook of Combinatorial Optimization, vol.\u00a03, Kluwer Academic Publishers (1998)","DOI":"10.1007\/978-1-4613-0303-9_25"},{"issue":"3","key":"2_CR8","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/s00453-010-9427-8","volume":"61","author":"I. Caragiannis","year":"2011","unstructured":"Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. Algorithmica\u00a061(3), 606\u2013637 (2011)","journal-title":"Algorithmica"},{"key":"2_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-540-27836-8_31","volume-title":"Automata, Languages and Programming","author":"G. Christodoulou","year":"2004","unstructured":"Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 345\u2013357. Springer, Heidelberg (2004)"},{"key":"2_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/978-3-642-35311-6_26","volume-title":"Internet and Network Economics","author":"J. Cohen","year":"2012","unstructured":"Cohen, J., D\u00fcrr, C., Thang, N.K.: Smooth inequalities and equilibrium inefficiency in scheduling games. In: Goldberg, P.W. (ed.) WINE 2012. LNCS, vol.\u00a07695, pp. 350\u2013363. Springer, Heidelberg (2012)"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Cole, R., Correa, J.R., Gkatzelis, V., Mirrokni, V.S., Olver Inner, N.: product spaces for MinSum coordination mechanisms. In: STOC (2011)","DOI":"10.1145\/1993636.1993708"},{"key":"2_CR12","unstructured":"Cole, R., Correa, J.R., Gkatzelis, V., Mirrokni, V., Olver, N.: Decentralized utilitarian mechanisms for scheduling games. In: Game. Econ. Behav. (to appear)"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1002\/nav.21497","volume":"59","author":"J.R. Correa","year":"2012","unstructured":"Correa, J.R., Queyranne, M.: Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost. Naval Res. Logist.\u00a059, 384\u2013395 (2012)","journal-title":"Naval Res. Logist."},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Czumaj, A., V\u00f6cking, B.: Tight bounds for worst-case equilibria. ACM T. Algo.\u00a03 (2007)","DOI":"10.1145\/1186810.1186814"},{"issue":"4","key":"2_CR15","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1145\/322276.322284","volume":"28","author":"E. Davis","year":"1981","unstructured":"Davis, E., Jaffe, J.M.: Algorithms for scheduling tasks on unrelated processors. J. ACM\u00a028(4), 721\u2013736 (1981)","journal-title":"J. ACM"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-04645-2_13","volume-title":"Algorithmic Game Theory","author":"C. D\u00fcrr","year":"2009","unstructured":"D\u00fcrr, C., Nguyen, K.T.: Non-clairvoyant scheduling games. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol.\u00a05814, pp. 135\u2013146. Springer, Heidelberg (2009)"},{"key":"2_CR17","unstructured":"Farzad, B., Olver, N., Vetta, A.: A priority-based model of routing. Chic. J. Theor. Comput. (2008)"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01930985","volume":"19","author":"G. Finn","year":"1979","unstructured":"Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT\u00a019, 312\u2013320 (1979)","journal-title":"BIT"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Fleischer, L., Svitkina, Z.: Preference-constrained oriented matching. In: ANALCO (2010)","DOI":"10.1137\/1.9781611973006.9"},{"issue":"2","key":"2_CR20","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1287\/opre.1090.0732","volume":"58","author":"B. Heydenreich","year":"2010","unstructured":"Heydenreich, B., M\u00fcller, R., Uetz, M.: Mechanism Design for Decentralized Online Machine Scheduling. Oper. Res.\u00a058(2), 445\u2013457 (2010)","journal-title":"Oper. Res."},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/3-540-69346-7_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"H. Hoogeveen","year":"1998","unstructured":"Hoogeveen, H., Schuurman, P., Woeginger, G.J.: Non-approximability results for scheduling problems with minsum criteria. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol.\u00a01412, p. 353. Springer, Heidelberg (1998)"},{"key":"2_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-642-29116-6_22","volume-title":"Approximation and Online Algorithms","author":"R. Hoeksma","year":"2012","unstructured":"Hoeksma, R., Uetz, M.: The Price of Anarchy for Minsum Related Machine Scheduling. In: Solis-Oba, R., Persiano, G. (eds.) WAOA 2011. LNCS, vol.\u00a07164, pp. 261\u2013273. Springer, Heidelberg (2012)"},{"issue":"3","key":"2_CR23","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1287\/opre.21.3.846","volume":"21","author":"W.A. Horn","year":"1973","unstructured":"Horn, W.A.: Minimizing average flow time with parallel machines. Oper. Res.\u00a021(3), 846\u2013847 (1973)","journal-title":"Oper. Res."},{"issue":"2","key":"2_CR24","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1145\/322003.322011","volume":"24","author":"O.H. Ibarra","year":"1977","unstructured":"Ibarra, O.H., Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM\u00a024(2), 280\u2013289 (1977)","journal-title":"J. ACM"},{"issue":"17","key":"2_CR25","doi-asserted-by":"publisher","first-page":"1589","DOI":"10.1016\/j.tcs.2008.12.032","volume":"410","author":"N. Immorlica","year":"2009","unstructured":"Immorlica, N., Li, L., Mirrokni, V.S., Schulz, A.S.: Coordination mechanisms for selfish scheduling. Theor. Comput. Sci.\u00a0410(17), 1589\u20131598 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/3-540-49116-3_38","volume-title":"STACS 99","author":"E. Koutsoupias","year":"1999","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, p. 404. Springer, Heidelberg (1999)"},{"key":"2_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-540-92185-1_30","volume-title":"Internet and Network Economics","author":"P. Lu","year":"2008","unstructured":"Lu, P., Yu, C.: Worst-Case Nash Equilibria in Restricted Routing. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol.\u00a05385, pp. 231\u2013238. Springer, Heidelberg (2008)"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"J. Nash","year":"1950","unstructured":"Nash, J.: Equilibrium points in N-person games. PNAS\u00a036, 48\u201349 (1950)","journal-title":"PNAS"},{"issue":"1","key":"2_CR29","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1057\/jors.2009.2","volume":"60","author":"C.N. Potts","year":"2009","unstructured":"Potts, C.N., Strusevich, V.: Fifty years of scheduling: a survey of milestones. J Oper. Res. Society\u00a060(1), 41\u201368 (2009)","journal-title":"J Oper. Res. Society"},{"key":"2_CR30","doi-asserted-by":"crossref","unstructured":"Rahn, M., Sch\u00e4fer, G.: Bounding the inefficiency of altruism through social contribution games (2013) (manuscript )","DOI":"10.1007\/978-3-642-45046-4_32"},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: STOC (2009)","DOI":"10.1145\/1536414.1536485"},{"key":"2_CR32","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"S. Sahni","year":"1980","unstructured":"Sahni, S., Cho, Y.: Bounds for list schedules on uniform processors. SIAM J. Comput.\u00a09, 91\u2013103 (1980)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2_CR33","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/S0895480199357078","volume":"15","author":"A.S. Schulz","year":"2002","unstructured":"Schulz, A.S., Skutella, M.: Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math.\u00a015(4), 450\u2013469 (2002)","journal-title":"SIAM J. Discrete Math."},{"key":"2_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/3-540-45535-3_29","volume-title":"Integer Programming and Combinatorial Optimization","author":"P. Schuurman","year":"2001","unstructured":"Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, p. 370. Springer, Heidelberg (2001)"},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"Sethuraman, J., Squillante, M.S.: Optimal scheduling of multiclass parallel machines. In: SODA (1999)","DOI":"10.1145\/301453.301483"},{"issue":"2","key":"2_CR36","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1145\/375827.375840","volume":"48","author":"M. Skutella","year":"2001","unstructured":"Skutella, M.: Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM\u00a048(2), 206\u2013242 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"2_CR37","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1287\/moor.25.1.63.15212","volume":"25","author":"M. Skutella","year":"2000","unstructured":"Skutella, M., Woeginger, G.J.: A ptas for minimizing the total weighted completion time on identical parallel machines. Math. Oper. Res.\u00a025(1), 63\u201375 (2000)","journal-title":"Math. Oper. Res."},{"issue":"1-2","key":"2_CR38","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. Smith","year":"1956","unstructured":"Smith, W.: Various optimizers for single stage production. Naval Res. Logist. Quart.\u00a03(1-2), 59\u201366 (1956)","journal-title":"Naval Res. Logist. Quart."},{"key":"2_CR39","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1287\/ijoc.14.2.175.119","volume":"14","author":"T. Vredeveld","year":"2002","unstructured":"Vredeveld, T., Hurkens, C.: Experimental comparison of approximation algorithms for scheduling unrelated parallel machines. INFORMS J. Comput.\u00a014, 175\u2013189 (2002)","journal-title":"INFORMS J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44777-2_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T12:12:23Z","timestamp":1558959143000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44777-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662447765","9783662447772"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44777-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}