{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:24:27Z","timestamp":1725888267144},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_24","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T09:04:39Z","timestamp":1495530279000},"page":"292-304","source":"Crossref","is-referenced-by-count":2,"title":["Breaking $$1 - 1\/e$$ Barrier for Non-preemptive Throughput Maximization"],"prefix":"10.1007","author":[{"given":"Sungjin","family":"Im","sequence":"first","affiliation":[]},{"given":"Shi","family":"Li","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"issue":"6","key":"24_CR1","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/s00224-002-1001-6","volume":"35","author":"M Adler","year":"2002","unstructured":"Adler, M., Rosenberg, A.L., Sitaraman, R.K., Unger, W.: Scheduling time-constrained communication in linear networks. Theor. Comput. Syst. 35(6), 599\u2013623 (2002)","journal-title":"Theor. Comput. Syst."},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.L., Khandekar, R., Pruhs, K., Stein, C., Schieber, B.: Non-preemptive min-sum scheduling with resource augmentation. In: FOCS, pp. 614\u2013624 (2007)","DOI":"10.1109\/FOCS.2007.11"},{"issue":"4","key":"24_CR3","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0167-6377(98)00045-5","volume":"24","author":"P Baptiste","year":"1999","unstructured":"Baptiste, P.: An O(\n            $$n^4$$\n          ) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Oper. Res. Lett. 24(4), 175\u2013180 (1999)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"24_CR4","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput. 31(2), 331\u2013352 (2001)","journal-title":"SIAM J. Comput."},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Berman, P., DasGupta, B.: Improvements in throughout maximization for real-time scheduling. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 680\u2013687. ACM (2000)","DOI":"10.1145\/335305.335401"},{"key":"24_CR6","volume-title":"Scheduling Computer and Manufacturing Processes","author":"J B\u0142a\u017cewicz","year":"2013","unstructured":"B\u0142a\u017cewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Weglarz, J.: Scheduling Computer and Manufacturing Processes. Springer Science & Business Media, Heidelberg (2013)"},{"issue":"4","key":"24_CR7","doi-asserted-by":"crossref","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. 31(4), 730\u2013738 (2006)","journal-title":"Math. Oper. Res."},{"issue":"6","key":"24_CR8","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.35.6.849","volume":"35","author":"M Fischetti","year":"1987","unstructured":"Fischetti, M., Martello, S., Toth, P.: The fixed job schedule problem with spread-time constraints. Oper. Res. 35(6), 849\u2013858 (1987)","journal-title":"Oper. Res."},{"issue":"3","key":"24_CR9","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0206029","volume":"6","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: Two-processor scheduling with start-times and deadlines. SIAM J. Comput. 6(3), 416\u2013426 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"24_CR10","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/0377-2217(94)90385-9","volume":"78","author":"NG Hall","year":"1994","unstructured":"Hall, N.G., Magazine, M.J.: Maximizing the value of a space mission. Eur. J. Oper. Res. 78(2), 224\u2013241 (1994)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"24_CR11","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF00365440","volume":"1","author":"KS Hong","year":"1989","unstructured":"Hong, K.S., Leung, J.Y.T.: Preemptive scheduling with release times and deadlines. Real Time Syst. 1(3), 265\u2013281 (1989)","journal-title":"Real Time Syst."},{"issue":"2","key":"24_CR12","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1137\/S0097539792236882","volume":"24","author":"G Koren","year":"1995","unstructured":"Koren, G., Shasha, D.: D\n            $$^{\\rm over}$$\n          : an optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems. SIAM J. Comput. 24(2), 318\u2013339 (1995)","journal-title":"SIAM J. Comput."},{"key":"24_CR13","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume":"4","author":"EL Lawler","year":"1993","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D.: Sequencing and scheduling: algorithms and complexity. Hanbooks Oper. Res. Manage. Sci. 4, 445\u2013522 (1993)","journal-title":"Hanbooks Oper. Res. Manage. Sci."},{"key":"24_CR14","unstructured":"Lipton, R.J., Tomkins, A.: Online interval scheduling. In: SODA, pp. 302\u2013311 (1994)"},{"key":"24_CR15","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-662-12788-9_6","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"C McDiarmid","year":"1998","unstructured":"McDiarmid, C.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms and Combinatorics, vol. 16, pp. 195\u2013248. Springer, Heidelberg (1998)"},{"issue":"5","key":"24_CR16","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y","volume":"2","author":"FC Spieksma","year":"1999","unstructured":"Spieksma, F.C.: On the approximability of an interval scheduling problem. J. Sched. 2(5), 215\u2013227 (1999)","journal-title":"J. Sched."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T09:10:56Z","timestamp":1495530656000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}