{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:26:38Z","timestamp":1743049598861,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642299513"},{"type":"electronic","value":"9783642299520"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29952-0_25","type":"book-chapter","created":{"date-parts":[[2012,5,3]],"date-time":"2012-05-03T06:14:09Z","timestamp":1336025649000},"page":"225-236","source":"Crossref","is-referenced-by-count":2,"title":["Coordination Mechanisms for Selfish Parallel Jobs Scheduling"],"prefix":"10.1007","author":[{"given":"Deshi","family":"Ye","sequence":"first","affiliation":[]},{"given":"Guochuan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","unstructured":"Azar, Y., Jain, K., Mirrokni, V.: (Almost) optimal coordination mechanisms for unrelated machine scheduling. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 323\u2013332 (2008)"},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"B.S. Baker","year":"1980","unstructured":"Baker, B.S., Coffman, E.G., Rivest, R.L.: Orthogonal packings in two dimensions. SIAM Journal on Computing\u00a09, 846\u2013855 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1137\/0212033","volume":"12","author":"B.S. Baker","year":"1983","unstructured":"Baker, B.S., Schwartz, J.S.: Shelf algorithms for two-dimensional packing problems. SIAM Journal on Computing\u00a012, 508\u2013525 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-642-15277-1_16","volume-title":"Euro-Par 2010 - Parallel Processing","author":"M. Bougeret","year":"2010","unstructured":"Bougeret, M., Dutot, P.-F., Jansen, K., Otte, C., Trystram, D.: A Fast 5\/2-Approximation Algorithm for Hierarchical Scheduling. In: D\u2019Ambra, P., Guarracino, M., Talia, D. (eds.) Euro-Par 2010. LNCS, vol.\u00a06271, pp. 157\u2013167. Springer, Heidelberg (2010)"},{"key":"25_CR5","series-title":"IFIP AICT","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/978-3-642-15240-5_23","volume-title":"Theoretical Computer Science","author":"M. Bougeret","year":"2010","unstructured":"Bougeret, M., Dutot, P.F., Jansen, K., Otte, C., Trystram, D.: Approximating the Non-contiguous Multiple Organization Packing Problem. In: Calude, C.S., Sassone, V. (eds.) TCS 2010. IFIP AICT, vol.\u00a0323, pp. 316\u2013327. Springer, Heidelberg (2010)"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-12450-1_4","volume-title":"Approximation and Online Algorithms","author":"M. Bougeret","year":"2010","unstructured":"Bougeret, M., Dutot, P.F., Jansen, K., Otte, C., Trystram, D.: Approximation Algorithms for Multiple Strip Packing. In: Bampis, E., Jansen, K. (eds.) WAOA 2009. LNCS, vol.\u00a05893, pp. 37\u201348. Springer, Heidelberg (2010)"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Caragiannis, I.: Efficient coordination mechanisms for unrelated machine scheduling. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 815\u2013824 (2009)","DOI":"10.1137\/1.9781611973068.89"},{"issue":"1","key":"25_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y. Cho","year":"1980","unstructured":"Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM Journal on Computing\u00a09(1), 91\u2013103 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"25_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":"25_CR10","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"E.G. Coffman","year":"1980","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level oriented two-dimensional packing algorithms. SIAM Journal on Computing\u00a09, 808\u2013826 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR11","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1137\/0213044","volume":"13","author":"G. Dobson","year":"1984","unstructured":"Dobson, G.: Scheduling independent tasks on uniform processors. SIAM Journal on Computing\u00a013, 705\u2013716 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR12","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1137\/0216037","volume":"16","author":"D.K. Friesen","year":"1987","unstructured":"Friesen, D.K.: Tighter bounds for LPT scheduling on uniform processors. SIAM Journal on Computing\u00a016, 554\u2013560 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/978-3-642-22300-6_40","volume-title":"Algorithms and Data Structures","author":"R. Harren","year":"2011","unstructured":"Harren, R., Jansen, K., Pr\u00e4del, L., van Stee, R.: A (5\/3 + \u03b5)-Approximation for Strip Packing. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol.\u00a06844, pp. 475\u2013487. Springer, Heidelberg (2011)"},{"issue":"4","key":"25_CR14","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1111\/j.1937-5956.2007.tb00271.x","volume":"16","author":"B. Heydenreich","year":"2007","unstructured":"Heydenreich, B., M\u00fcller, R., Uetz, M.: Games and mechanism design in machine scheduling-an introduction. Production and Operations Management\u00a016(4), 437\u2013454 (2007)","journal-title":"Production and Operations Management"},{"key":"25_CR15","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.E., Mirrokni, V.S., Schulz, A.S.: Coordination mechanisms for selfish scheduling. Theoretical Computer Science\u00a0410, 1589\u20131598 (2009)","journal-title":"Theoretical Computer Science"},{"key":"25_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-540-74456-6_11","volume-title":"Mathematical Foundations of Computer Science 2007","author":"K. Jansen","year":"2007","unstructured":"Jansen, K., Solis-Oba, R.: New Approximability Results for 2-Dimensional Packing Problems. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 103\u2013114. Springer, Heidelberg (2007)"},{"issue":"5","key":"25_CR17","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s10951-006-8497-6","volume":"9","author":"B. Johannes","year":"2006","unstructured":"Johannes, B.: Scheduling parallel jobs to minimize the makespan. Journal of Scheduling\u00a09(5), 433\u2013452 (2006)","journal-title":"Journal of Scheduling"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"Kenyon, C., Remila, E.: Approximate Strip Packing. In: Proc. 37th Symp. Foundations of Computer Science (FOCS), vol.\u00a037, pp. 31\u201337 (1996)","DOI":"10.1109\/SFCS.1996.548461"},{"key":"25_CR19","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, pp. 404\u2013413. Springer, Heidelberg (1999)"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic game theory. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511800481"},{"key":"25_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BFb0049416","volume-title":"Algorithms - ESA \u201994","author":"I. Schiermeyer","year":"1994","unstructured":"Schiermeyer, I.: Reverse-Fit: A 2-Optimal Algorithm for Packing Rectangles. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 290\u2013299. Springer, Heidelberg (1994)"},{"issue":"1","key":"25_CR22","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1287\/ijoc.1050.0152","volume":"19","author":"P. Schuurman","year":"2007","unstructured":"Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. Informs Journal on Computing\u00a019(1), 52\u201363 (2007)","journal-title":"Informs Journal on Computing"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"Schwiegelshohn, U., Tchernykh, A., Yahyapour, R.: Online scheduling in grids. In: IEEE International Symposium on Parallel and Distributed Processing (IPDPS), pp. 1\u201310 (2008)","DOI":"10.1109\/IPDPS.2008.4536273"},{"key":"25_CR24","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0097539793255801","volume":"26","author":"A. Steinberg","year":"1997","unstructured":"Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM Journal on Computing\u00a026, 401\u2013409 (1997)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"25_CR25","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10878-007-9125-x","volume":"17","author":"D. Ye","year":"2009","unstructured":"Ye, D., Han, X., Zhang, G.: A note on online strip packing. Journal of Combinatorial Optimization\u00a017(4), 417\u2013423 (2009)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"25_CR26","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.tcs.2009.09.029","volume":"412","author":"D. Ye","year":"2011","unstructured":"Ye, D., Han, X., Zhang, G.: Online multiple-strip packing. Theoretical Computer Science\u00a0412(3), 233\u2013239 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"25_CR27","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10951-007-0032-x","volume":"10","author":"D. Ye","year":"2007","unstructured":"Ye, D., Zhang, G.: On-line scheduling of parallel jobs in a list. Journal of Scheduling\u00a010(6), 407\u2013413 (2007)","journal-title":"Journal of Scheduling"},{"issue":"1","key":"25_CR28","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1515\/156939206776241264","volume":"16","author":"S. Zhuk","year":"2006","unstructured":"Zhuk, S.: Approximate algorithms to pack rectangles into several strips. Discrete Mathematics and Applications\u00a016(1), 73\u201385 (2006)","journal-title":"Discrete Mathematics and Applications"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29952-0_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:54:57Z","timestamp":1743044097000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-29952-0_25"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642299513","9783642299520"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29952-0_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}