{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T18:19:23Z","timestamp":1773944363730,"version":"3.50.1"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031498145","type":"print"},{"value":"9783031498152","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-49815-2_13","type":"book-chapter","created":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T07:02:28Z","timestamp":1703142148000},"page":"175-189","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Any-Order Online Interval Selection"],"prefix":"10.1007","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[]},{"given":"Christodoulos","family":"Karavasilis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,22]]},"reference":[{"issue":"2","key":"13_CR1","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1023\/A:1022933824889","volume":"6","author":"R Adler","year":"2003","unstructured":"Adler, R., Azar, Y.: Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms. J. Scheduling 6(2), 113\u2013129 (2003)","journal-title":"J. Scheduling"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Azar, Y., Gutner, S.: Admission control to minimize rejections and online set cover with repetitions. In: Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 238\u2013244 (2005)","DOI":"10.1145\/1073970.1074010"},{"key":"13_CR3","unstructured":"Awerbuch, B., Bartal, Y., Fiat, A., Ros\u00e9n, A.: Competitive non-preemptive call control. In: SODA, vol. 94, pp. 312\u2013320. Citeseer (1994)"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Hartline, J.D., Kleinberg, R.D.: Selling ad campaigns: online algorithms with cancellations. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 61\u201370 (2009)","DOI":"10.1145\/1566374.1566383"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2013.10.004","volume":"233","author":"UT Bachmann","year":"2013","unstructured":"Bachmann, U.T., Halld\u00f3rsson, M.M., Shachnai, H.: Online selection of intervals and t-intervals. Inf. Comput. 233, 1\u201311 (2013)","journal-title":"Inf. Comput."},{"issue":"1\u20133","key":"13_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0166-218X(99)00238-3","volume":"103","author":"P Baptiste","year":"2000","unstructured":"Baptiste, P.: Scheduling equal-length jobs on identical parallel machines. Discret. Appl. Math. 103(1\u20133), 21\u201332 (2000)","journal-title":"Discret. Appl. Math."},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-44634-6_15","volume-title":"Algorithms and Data Structures","author":"A Blum","year":"2001","unstructured":"Blum, A., Kalai, A., Kleinberg, J.: Admission control to minimize rejections. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 155\u2013164. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44634-6_15"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Bogart, K.P., West, D.B.: A short proof that \u201cproper= unit.\u201d Discret. Math. 201(1\u20133), 21\u201323 (1999)","DOI":"10.1016\/S0012-365X(98)00310-0"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2011.11.010","volume":"418","author":"A Borodin","year":"2012","unstructured":"Borodin, A., Ivan, I., Ye, Y., Zimny, B.: On sum coloring and sum multi-coloring for restricted families of graphs. Theor. Comput. Sci. 418, 1\u201313 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Borodin, A., Karavasilis, C.: Any-order online interval selection. arXiv preprint arXiv:2303.06127 (2023)","DOI":"10.1007\/978-3-031-49815-2_13"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Canetti, R., Irani, S.: Bounding the power of preemption in randomized scheduling. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 606\u2013615 (1995)","DOI":"10.1145\/225058.225278"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-030-80879-2_10","volume-title":"Approximation and Online Algorithms","author":"D Christou","year":"2021","unstructured":"Christou, D., Fotakis, D., Koumoutsos, G.: Memoryless algorithms for\u00a0the\u00a0generalized k-server problem on\u00a0uniform metrics. In: Kaklamanis, C., Levin, A. (eds.) WAOA 2020. LNCS, vol. 12806, pp. 143\u2013158. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-80879-2_10"},{"issue":"1","key":"13_CR13","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10951-006-5595-4","volume":"9","author":"M Chrobak","year":"2006","unstructured":"Chrobak, M., D\u00fcrr, C., Jawor, W., Kowalik, \u0141, Kurowski, M.: A note on scheduling equal-length jobs to maximize throughput. J. Scheduling 9(1), 71\u201373 (2006)","journal-title":"J. Scheduling"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Coester, C., Koutsoupias, E.: The online k-taxi problem. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019)","DOI":"10.1145\/3313276.3316370"},{"issue":"4","key":"13_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2886102","volume":"12","author":"Y Emek","year":"2016","unstructured":"Emek, Y., Halld\u00f3rsson, M.M., Ros\u00e9n, A.: Space-constrained interval selection. ACM Trans. Algorithms (TALG) 12(4), 1\u201332 (2016)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/978-3-540-87744-8_32","volume-title":"Algorithms - ESA 2008","author":"L Epstein","year":"2008","unstructured":"Epstein, L., Levin, A.: Improved randomized results for that interval selection problem. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 381\u2013392. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87744-8_32"},{"issue":"1","key":"13_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0166-218X(95)00112-5","volume":"58","author":"U Faigle","year":"1995","unstructured":"Faigle, U., Nawijn, W.M.: Note on scheduling intervals on-line. Discret. Appl. Math. 58(1), 13\u201317 (1995)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"13_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9049-y","volume":"50","author":"D Fotakis","year":"2008","unstructured":"Fotakis, D.: On the competitive ratio for online facility location. Algorithmica 50(1), 1\u201357 (2008)","journal-title":"Algorithmica"},{"issue":"10","key":"13_CR19","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/j.ipl.2012.01.015","volume":"112","author":"SP Fung","year":"2012","unstructured":"Fung, S.P., Poon, C.K., Yung, D.K.: On-line scheduling of equal-length intervals on parallel machines. Inf. Process. Lett. 112(10), 376\u2013379 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"13_CR20","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/s00224-013-9528-2","volume":"55","author":"SP Fung","year":"2014","unstructured":"Fung, S.P., Poon, C.K., Zheng, F.: Improved randomized online scheduling of intervals and jobs. Theory Comput. Syst. 55(1), 202\u2013228 (2014)","journal-title":"Theory Comput. Syst."},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Garay, J.A., Gopal, I.S.: Call preemption in communication networks. In: Proceedings IEEE INFOCOM 1992: Conference on Computer Communications (1992)","DOI":"10.1109\/INFCOM.1992.263457"},{"issue":"1","key":"13_CR22","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jagm.1996.0821","volume":"23","author":"JA Garay","year":"1997","unstructured":"Garay, J.A., Gopal, I.S., Kutten, S., Mansour, Y., Yung, M.: Efficient on-line call control algorithms. J. Algorithms 23(1), 180\u2013194 (1997)","journal-title":"J. Algorithms"},{"issue":"2","key":"13_CR23","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/s00224-012-9408-1","volume":"53","author":"MM Halld\u00f3rsson","year":"2013","unstructured":"Halld\u00f3rsson, M.M., Patt-Shamir, B., Rawitz, D.: Online scheduling with interval conflicts. Theory Comput. Syst. 53(2), 300\u2013317 (2013)","journal-title":"Theory Comput. Syst."},{"key":"13_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-32241-9_6","volume-title":"Computing and Combinatorics","author":"X Han","year":"2012","unstructured":"Han, X., Kawase, Y., Makino, K.: Online Knapsack problem with removal cost. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 61\u201373. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32241-9_6"},{"key":"13_CR25","unstructured":"Hyatt-Denesik, D., Rahgoshay, M., Salavatipour, M.R.: Approximations for throughput maximization. arXiv preprint arXiv:2001.10037 (2020)"},{"issue":"1","key":"13_CR26","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0020-0190(94)90138-4","volume":"52","author":"JM Kleinberg","year":"1994","unstructured":"Kleinberg, J.M.: A lower bound for two-server balancing algorithms. Inf. Process. Lett. 52(1), 39\u201343 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"13_CR27","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1002\/nav.20231","volume":"54","author":"AW Kolen","year":"2007","unstructured":"Kolen, A.W., Lenstra, J.K., Papadimitriou, C.H., Spieksma, F.C.: Interval scheduling: a survey. Nav. Res. Logist. (NRL) 54(5), 530\u2013543 (2007)","journal-title":"Nav. Res. Logist. (NRL)"},{"issue":"2","key":"13_CR28","first-page":"105","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E.: The k-server problem. CS Rev. 3(2), 105\u2013118 (2009)","journal-title":"CS Rev."},{"issue":"2\u20133","key":"13_CR29","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2004.06.002","volume":"324","author":"E Koutsoupias","year":"2004","unstructured":"Koutsoupias, E., Taylor, D.S.: The CNN problem and other k-server variants. Theor. Comput. Sci. 324(2\u20133), 347\u2013359 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Kovalyov, M.Y., Ng, C.T., Cheng, T.E.: Fixed interval scheduling: models, applications, computational complexity and algorithms. Eur. J. OR (2007)","DOI":"10.1016\/j.ejor.2006.01.049"},{"key":"13_CR31","unstructured":"Lipton, R.J., Tomkins, A.: Online interval scheduling. In: SODA, vol. 94 (1994)"},{"issue":"4","key":"13_CR32","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1023\/B:JOSH.0000031423.39762.d3","volume":"7","author":"H Miyazawa","year":"2004","unstructured":"Miyazawa, H., Erlebach, T.: An improved randomized on-line algorithm for a weighted interval selection problem. J. Sched. 7(4), 293\u2013311 (2004)","journal-title":"J. Sched."},{"key":"13_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/BFb0035792","volume-title":"Automata, Languages and Programming","author":"P Raghavan","year":"1989","unstructured":"Raghavan, P., Snir, M.: Memory versus randomization in on-line algorithms. In: Ausiello, G., Dezani-Ciancaglini, M., Della Rocca, S.R. (eds.) ICALP 1989. LNCS, vol. 372, pp. 687\u2013703. Springer, Heidelberg (1989). https:\/\/doi.org\/10.1007\/BFb0035792"},{"issue":"4\u20135","key":"13_CR34","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0167-6377(98)00019-4","volume":"22","author":"SS Seiden","year":"1998","unstructured":"Seiden, S.S.: Randomized online interval scheduling. Oper. Res. Lett. 22(4\u20135), 171\u2013177 (1998)","journal-title":"Oper. Res. Lett."},{"key":"13_CR35","doi-asserted-by":"crossref","unstructured":"Sgall, J.: On-line scheduling. Online Algorithms, pp. 196\u2013231 (1998)","DOI":"10.1007\/BFb0029570"},{"issue":"3","key":"13_CR36","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0020-0190(95)00147-5","volume":"56","author":"A Tomkins","year":"1995","unstructured":"Tomkins, A.: Lower bounds for two call control problems. Inf. Process. Lett. 56(3), 173\u2013178 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"13_CR37","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0304-3975(94)90150-3","volume":"130","author":"GJ Woeginger","year":"1994","unstructured":"Woeginger, G.J.: On-line scheduling of jobs with fixed start and end times. Theor. Comput. Sci. 130(1), 5\u201316 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"13_CR38","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s11590-017-1191-0","volume":"12","author":"G Yu","year":"2018","unstructured":"Yu, G., Jacobson, S.H.: Online c-benevolent job scheduling on multiple machines. Optim. Lett. 12(2), 251\u2013263 (2018)","journal-title":"Optim. Lett."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49815-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,28]],"date-time":"2023-12-28T23:04:44Z","timestamp":1703804684000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49815-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031498145","9783031498152"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49815-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"22 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo-conference.org\/2023\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"16","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.05","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7.7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}