{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T22:33:50Z","timestamp":1772490830402,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,1,5]],"date-time":"2008-01-05T00:00:00Z","timestamp":1199491200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s10878-007-9131-z","type":"journal-article","created":{"date-parts":[[2008,1,4]],"date-time":"2008-01-04T10:29:12Z","timestamp":1199442552000},"page":"248-262","source":"Crossref","is-referenced-by-count":20,"title":["Online interval scheduling: randomized\u00a0and\u00a0multiprocessor\u00a0cases"],"prefix":"10.1007","volume":"16","author":[{"given":"Stanley P. Y.","family":"Fung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chung Keung","family":"Poon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feifeng","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,5]]},"reference":[{"key":"9131_CR1","unstructured":"Awerbuch B, Bartal Y, Fiat A, Rosen A (1994) Competitive non-preemptive call control. In: Proceedings of 5th ACM-SIAM symposium on discrete algorithms, pp 312\u2013320"},{"key":"9131_CR2","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF00365406","volume":"4","author":"S Baruah","year":"1992","unstructured":"Baruah S, Koren G, Mao D, Mishra B, Raghunathan A, Rosier L, Shasha D, Wang F (1992) On the competitiveness of on-line real-time task scheduling. Real-Time Syst 4:125\u2013144","journal-title":"Real-Time Syst"},{"key":"9131_CR3","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0012-365X(98)00310-0","volume":"201","author":"KP Bogart","year":"1999","unstructured":"Bogart KP, West DB (1999) A short proof that proper\u2009=\u2009unit. Discrete Math 201:21\u201323","journal-title":"Discrete Math"},{"key":"9131_CR4","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"1998","unstructured":"Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, New York"},{"issue":"4","key":"9131_CR5","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1137\/S0097539795283292","volume":"27","author":"R Canetti","year":"1998","unstructured":"Canetti R, Irani S (1998) Bounding the power of preemption in randomized scheduling. SIAM J Comput 27(4):993\u20131015","journal-title":"SIAM J Comput"},{"key":"9131_CR6","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/978-3-540-27798-9_24","volume-title":"Proceedings of 10th international computing and combinatorics conference","author":"W-T Chan","year":"2004","unstructured":"Chan W-T, Lam T-W, Ting H-F, Wong PWH (2004) New results on on-demand broadcasting with deadline via job scheduling with cancellation. In: Proceedings of 10th international computing and combinatorics conference. Lecture notes in computer science, vol 3106. Springer, Berlin, pp 210\u2013218"},{"key":"9131_CR7","unstructured":"Faigle U, Nawijn WM (1991) Greedy k-coverings of interval orders (Technical Report 979). University of Twente"},{"key":"9131_CR8","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/11560586_21","volume-title":"Proceedings of 9th Italian conference on theoretical computer science","author":"SPY Fung","year":"2005","unstructured":"Fung SPY, Chin FYL, Poon CK (2005) Laxity helps in broadcast scheduling. In: Proceedings of 9th Italian conference on theoretical computer science. Lecture notes in computer science, vol 3701. Springer, Berlin, pp 251\u2013264"},{"issue":"3","key":"9131_CR9","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1016\/j.tcs.2004.02.047","volume":"325","author":"J-H Kim","year":"2004","unstructured":"Kim J-H, Chwa K-Y (2004) Scheduling broadcasts with deadlines. Theor Comput Sci 325(3):479\u2013488","journal-title":"Theor Comput Sci"},{"issue":"1\u20132","key":"9131_CR10","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0304-3975(94)90165-1","volume":"128","author":"G Koren","year":"1994","unstructured":"Koren G, Shasha D (1994) Moca: A multiprocessor on-line competitive algorithm for real-time system scheduling. Theor Comput Sci 128(1\u20132):75\u201397","journal-title":"Theor Comput Sci"},{"key":"9131_CR11","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1137\/S0097539792236882","volume":"24","author":"G Koren","year":"1995","unstructured":"Koren G, Shasha D (1995) D over : An optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems. SIAM J Comput 24:318\u2013339","journal-title":"SIAM J Comput"},{"key":"9131_CR12","unstructured":"Lipton RJ, Tomkins A (1994) Online interval scheduling. In: Proceedings of 5th ACM-SIAM symposium on discrete algorithms, pp 302\u2013311"},{"issue":"4","key":"9131_CR13","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1023\/B:JOSH.0000031423.39762.d3","volume":"7","author":"H Miyazawa","year":"2004","unstructured":"Miyazawa H, Erlebach T (2004) An improved randomized on-line algorithm for a weighted interval selection problem. J Sched 7(4):293\u2013311","journal-title":"J Sched"},{"issue":"4\u20135","key":"9131_CR14","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/S0167-6377(98)00019-4","volume":"22","author":"SS Seiden","year":"1998","unstructured":"Seiden SS (1998) Randomized online interval scheduling. Oper Res Lett 22(4\u20135):171\u2013177","journal-title":"Oper Res Lett"},{"key":"9131_CR15","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/11758471_18","volume-title":"Proceedings of 6th Italian conference on algorithms and complexity","author":"H-F Ting","year":"2006","unstructured":"Ting H-F (2006) A near optimal scheduler for on-demand data broadcasts. In: Proceedings of 6th Italian conference on algorithms and complexity. Lecture notes in computer science, vol 3998. Springer, Berlin, pp 163\u2013174"},{"issue":"1","key":"9131_CR16","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0304-3975(94)90150-3","volume":"130","author":"GJ Woeginger","year":"1994","unstructured":"Woeginger GJ (1994) On-line scheduling of jobs with fixed start and end times. Theor Comput Sci 130(1):5\u201316","journal-title":"Theor Comput Sci"},{"key":"9131_CR17","doi-asserted-by":"crossref","unstructured":"Yao AC-C (1977) Probabilistic computations: towards a unified measure of complexity. In: Proceedings of 18th IEEE symposium on foundations of computer science, pp 222\u2013227","DOI":"10.1109\/SFCS.1977.24"},{"key":"9131_CR18","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/11809678_34","volume-title":"Proceedings of 12th international computing and combinatorics conference","author":"F Zheng","year":"2006","unstructured":"Zheng F, Fung SPY, Chan W-T, Chin FYL, Poon CK, Wong PWH (2006) Improved on-line broadcast scheduling with deadlines. In: Proceedings of 12th international computing and combinatorics conference. Lecture notes in computer science, vol 4112. Springer, Berlin, pp 320\u2013329"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9131-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9131-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9131-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:12Z","timestamp":1559261892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9131-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,5]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9131"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9131-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,5]]}}}