{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:12:55Z","timestamp":1759637575751,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642352607"},{"type":"electronic","value":"9783642352614"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-35261-4_11","type":"book-chapter","created":{"date-parts":[[2012,12,14]],"date-time":"2012-12-14T01:59:41Z","timestamp":1355450381000},"page":"75-84","source":"Crossref","is-referenced-by-count":3,"title":["Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem"],"prefix":"10.1007","author":[{"given":"Mong-Jen","family":"Kao","sequence":"first","affiliation":[]},{"given":"Jian-Jia","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Adler, M., Sitaraman, R., Rosenberg, A., Unger, W.: Scheduling time-constrained communication in linear networks. In: SPAA 1998, NY, pp. 269\u2013278 (1998)","key":"11_CR1","DOI":"10.1145\/277651.277693"},{"key":"11_CR2","first-page":"721","volume-title":"STOC 2006","author":"N. Bansal","year":"2006","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-ptas for unsplittable flow on line graphs. In: STOC 2006, pp. 721\u2013729. ACM, NY (2006)"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A. Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J.S., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM\u00a048, 1069\u20131090 (2001)","journal-title":"J. ACM"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A. Bar-Noy","year":"2002","unstructured":"Bar-Noy, A., Guha, S.: Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput.\u00a031, 331\u2013352 (2002)","journal-title":"SIAM J. Comput."},{"key":"11_CR5","volume-title":"Online computation and competitive analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, New York (1998)"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2000807.2000816","volume":"7","author":"G. Calinescu","year":"2011","unstructured":"Calinescu, G., Chakrabarti, A., Karloff, H., Rabani, Y.: An improved approximation algorithm for resource allocation. ACM Trans. Algorithms\u00a07, 48:1\u201348:7 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/978-3-642-03685-9_6","volume-title":"APPROX and RANDOM 2009","author":"J. Chuzhoy","year":"2009","unstructured":"Chuzhoy, J., Codenotti, P.: Resource Minimization Job Scheduling. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 70\u201383. Springer, Heidelberg (2009)"},{"doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Guha, S., Khanna, S., Naor, J.S.: Machine minimization for scheduling jobs with interval constraints. In: FOCS 2004, Washington, pp. 81\u201390 (2004)","key":"11_CR8","DOI":"10.1109\/FOCS.2004.38"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1145\/1183907.1183908","volume":"53","author":"J. Chuzhoy","year":"2006","unstructured":"Chuzhoy, J., Naor, J.S.: New hardness results for congestion minimization and machine scheduling. J. ACM\u00a053, 707\u2013721 (2006)","journal-title":"J. ACM"},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1287\/moor.1060.0218","volume":"31","author":"J. Chuzhoy","year":"2006","unstructured":"Chuzhoy, J., Ostrovsky, R., Rabani, Y.: Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res.\u00a031, 730\u2013738 (2006)","journal-title":"Math. Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"Cieliebak, M., Erlebach, T., Hennecke, F., Weber, B., Widmayer, P.: Scheduling with release times and deadlines on a minimum number of machines. IFIP, vol.\u00a0155, pp. 209\u2013222. Springer, Boston","key":"11_CR11","DOI":"10.1007\/1-4020-8141-3_18"},{"doi-asserted-by":"crossref","unstructured":"Crama, Y., Flippo, O., Klundert, J., Spieksma, F.: The assembly of printed circuit boards: A case with multiple machines and multiple board types (1998)","key":"11_CR12","DOI":"10.1016\/S0377-2217(96)00228-7"},{"key":"11_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Tompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica\u00a07, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1023\/A:1019156211458","volume":"3","author":"G. Rajugopal","year":"1998","unstructured":"Rajugopal, G., Hafez, R.: Adaptive rate controlled, robust video communication over packet wireless networks. Mob. Netw. Appl.\u00a03, 33\u201347 (1998)","journal-title":"Mob. Netw. Appl."},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.tcs.2007.10.023","volume":"390","author":"Y. Shi","year":"2008","unstructured":"Shi, Y., Ye, D.: Online bin packing with arbitrary release times. Theoretical Computer Science\u00a0390, 110\u2013119 (2008)","journal-title":"Theoretical Computer Science"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y","volume":"2","author":"F. Spieksma","year":"1999","unstructured":"Spieksma, F.: On the approximability of an interval scheduling problem. Journal of Scheduling\u00a02, 215\u2013225 (1999)","journal-title":"Journal of Scheduling"},{"key":"11_CR18","first-page":"129","volume-title":"MULTIMEDIA 1996","author":"D. Yau","year":"1996","unstructured":"Yau, D., Lam, S.: Adaptive rate-controlled scheduling for multimedia applications. In: MULTIMEDIA 1996, pp. 129\u2013140. ACM, New York (1996)"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.orl.2009.01.008","volume":"37","author":"G. Yu","year":"2009","unstructured":"Yu, G., Zhang, G.: Scheduling with a minimum number of machines. Operations Research Letters\u00a037, 97\u2013101 (2009)","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35261-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T17:55:14Z","timestamp":1745430914000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35261-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642352607","9783642352614"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35261-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}