2 papers
cs.DS2026
Revisiting Real-Time Interval and Throughput Maximization
Allan Borodin, Changdao He, Nadim Mottu
Job throughput maximization is the central maximization problem in scheduling. Interval scheduling is the special case of throughput maximization when jobs are intervals and theref…
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…