{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T00:15:09Z","timestamp":1758672909920,"version":"3.44.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:p>Following a line of work that takes advantage of vast machine-learned data to enhance online algorithms with (possibly erroneous) information about future inputs, we consider predictions in the context of deterministic algorithms for the problem of selecting a maximum weight independent set of intervals arriving on the real line. We look at two weight functions, unit (constant) weights, and weights proportional to the interval\u2019s length. In the classical online model of irrevocable decisions, no algorithm can achieve constant competitiveness. In this setting, we show that a simple algorithm that is faithful to the predictions is optimal, and achieves an objective value of at least OPT - \u03b7, with \u03b7  being the total error in the predictions, both for unit, and proportional weights.\n\nWhen revocable acceptances (a form of preemption) are allowed, the optimal deterministic algorithm for unit weights is 2k-competitive, where k is the number of different interval lengths. We give an algorithm with performance OPT \u2212 \u03b7 (and therefore 1-consistent), that is also (2k + 1)-robust. For proportional weights, there is an optimal (2\u03c6 + 1)-competitive algorithm, where \u03c6  is the golden ratio. We present an algorithm with parameter \u03bb &gt; 1 that is 3\u03bb \/ (\u03bb  - 1) -consistent, and (4\u03bb^2 + 2\u03bb) \/ (\u03bb - 1)-robust. Although these bounds are not tight, we show that for \u03bb  &gt; 3.42 we achieve consistency better than the optimal online guarantee, while maintaining bounded robustness.\n\nWe conclude with some experimental results on real-world data that complement our theoretical findings, and show the benefit of prediction algorithms for online interval selection, even in the presence of high error.<\/jats:p>","DOI":"10.24963\/ijcai.2025\/948","type":"proceedings-article","created":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:10:40Z","timestamp":1758269440000},"page":"8527-8535","source":"Crossref","is-referenced-by-count":0,"title":["Interval Selection with Binary Predictions"],"prefix":"10.24963","author":[{"given":"Christodoulos","family":"Karavasilis","sequence":"first","affiliation":[{"name":"University of Toronto"}]}],"member":"10584","event":{"number":"34","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2025","name":"Thirty-Fourth International Joint Conference on Artificial Intelligence {IJCAI-25}","start":{"date-parts":[[2025,8,16]]},"theme":"Artificial Intelligence","location":"Montreal, Canada","end":{"date-parts":[[2025,8,22]]}},"container-title":["Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T11:35:35Z","timestamp":1758627335000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2025\/948"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2025,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2025\/948","relation":{},"subject":[],"published":{"date-parts":[[2025,9]]}}}