{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T04:13:16Z","timestamp":1748664796872,"version":"3.41.0"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319252575"},{"type":"electronic","value":"9783319252582"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-25258-2_7","type":"book-chapter","created":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T07:10:18Z","timestamp":1445238618000},"page":"91-103","source":"Crossref","is-referenced-by-count":1,"title":["A Randomized Algorithm for Online Scheduling with Interval Conflicts"],"prefix":"10.1007","author":[{"given":"Marcin","family":"Bienkowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Artur","family":"Kraska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,20]]},"reference":[{"key":"7_CR1","unstructured":"Awerbuch, B., Bartal, Y., Fiat, A., Ros\u00e9n, A.: Competitive non-preemptive call control. In: Proc. of the 5th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 312\u2013320 (1994)"},{"key":"#cr-split#-7_CR2.1","doi-asserted-by":"crossref","unstructured":"Bachmann, U.T., Halld\u00f3rsson, M.M., Shachnai, H.: Online selection of intervals and t-intervals. Information and Computation\u00a0233, 1-11 (2013)","DOI":"10.1016\/j.ic.2013.10.004"},{"key":"#cr-split#-7_CR2.2","unstructured":"Also appeared in Proc. of the 12th SWAT, pp. 383-394 (2010)"},{"key":"7_CR3","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)"},{"issue":"1","key":"7_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/2596583.2596603","volume":"45","author":"M. Chrobak","year":"2014","unstructured":"Chrobak, M.: Online aggregation problems. SIGACT News\u00a045(1), 91\u2013102 (2014)","journal-title":"SIGACT News"},{"key":"#cr-split#-7_CR5.1","doi-asserted-by":"crossref","unstructured":"Emek, Y., Halld\u00f3rsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing. SIAM Journal on Computing\u00a041(4), 728-746 (2012)","DOI":"10.1137\/110820774"},{"key":"#cr-split#-7_CR5.2","doi-asserted-by":"crossref","unstructured":"Also appeared as Online set packing and competitive scheduling of multi-part tasks. In: Proc. of the 29th PODC, pp. 440-449 (2010)","DOI":"10.1145\/1835698.1835800"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Garay, J.A., Gopal, I.S.: Call preemption in communication networks. In: Proc.\u00a0of the 11th IEEE Int. Conference on Computer Communications (INFOCOM), pp. 1043\u20131050 (1992)","DOI":"10.1109\/INFCOM.1992.263457"},{"issue":"1","key":"7_CR7","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jagm.1996.0821","volume":"23","author":"J.A. Garay","year":"1997","unstructured":"Garay, J.A., Gopal, I.S., Kutten, S., Mansour, Y., Yung, M.: Efficient on-line call control algorithms. Journal of Algorithms\u00a023(1), 180\u2013194 (1997)","journal-title":"Journal of Algorithms"},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-63397-9_16","volume-title":"Algorithms - ESA \u201997","author":"T. Garefalakis","year":"1997","unstructured":"Garefalakis, T.: A new family of randomized algorithms for list accessing. In: Burkard, R.E., Woeginger, G.J. (eds.) ESA 1997. LNCS, vol.\u00a01284, pp. 200\u2013216. Springer, Heidelberg (1997)"},{"key":"#cr-split#-7_CR9.1","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Patt-Shamir, B., Rawitz, D.: Online scheduling with interval conflicts. Theory of Computing Systems\u00a053(2), 300-317 (2013)","DOI":"10.1007\/s00224-012-9408-1"},{"key":"#cr-split#-7_CR9.2","unstructured":"Also appeared in Proc. of the 28th STACS, pp. 472-483 (2011)"},{"issue":"6","key":"7_CR10","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0020-0190(91)90086-W","volume":"38","author":"S. Irani","year":"1991","unstructured":"Irani, S.: Two results on the list update problem. Information Processing Letters\u00a038(6), 301\u2013306 (1991)","journal-title":"Information Processing Letters"},{"key":"7_CR11","unstructured":"Jaromczyk, J.W., Pezarski, A., \u015alusarek, M.: An optimal competitive on-line algorithm for the minimal clique cover problem in interval and circular-arc graphs. In: Proc.\u00a0of the 19th European Workshop on Computational Geometry, EWCG (2003)"},{"key":"7_CR12","unstructured":"Lipton, R.J., Tomkins, A.: Online interval scheduling. In: Proc.\u00a0of the 5th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 302\u2013311 (1994)"},{"issue":"1","key":"7_CR13","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF01294261","volume":"11","author":"N. Reingold","year":"1994","unstructured":"Reingold, N., Westbrook, J., Sleator, D.D.: Randomized competitive algorithms for the list update problem. Algorithmica\u00a011(1), 15\u201332 (1994)","journal-title":"Algorithmica"},{"issue":"2","key":"7_CR14","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-25258-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T02:17:37Z","timestamp":1748657857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25258-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319252575","9783319252582"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25258-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}