1 citations · 1 across the 4 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
Any-Order Online Interval Selection
Allan Borodin, Christodoulos Karavasilis
We consider the problem of online interval scheduling on a single machine, where intervals arrive online in an order chosen by an adversary, and the algorithm must output a set of…
An Experimental Study of Algorithms for Online Bipartite Matching
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
We perform an experimental study of algorithms for online bipartite matching under the known i.i.d. input model with integral types. In the last decade, there has been substantial…
Greedy Bipartite Matching in Random Type Poisson Arrival Model
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
We introduce a new random input model for bipartite matching which we call the Random Type Poisson Arrival Model. Just like in the known i.i.d. model (introduced by Feldman et al.…