3 papers
cs.DS2026
Deterministically Simulating Barely Random Algorithms in the Random-Order Arrival Model
Allan Borodin, Christodoulos Karavasilis, David Zhang
Interest in the random-order model (ROM) leads us to initiate a study of utilizing random-order arrivals to extract random bits with the goal of derandomizing algorithms. Besides p…
cs.DS2025
Random-Order Interval Selection
Allan Borodin, Christodoulos Karavasilis
In the problem of online unweighted interval selection, the objective is to maximize the number of non-conflicting intervals accepted by the algorithm. In the conventional online m…
cs.DS2025
Interval Selection with Binary Predictions
Christodoulos Karavasilis
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 predi…