10 citations · 39 across the 16 of their papers we have counts for
11 papers · 1 filter
Online Bipartite Matching in the Probe-Commit Model
Allan Borodin, Calum MacRury
We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they…
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…
Greedy Approaches to Online Stochastic Matching
Allan Borodin, Calum MacRury, Akash Rakheja
Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one-sided online bipartite matching problem where edges a…
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…
Advice Complexity of Priority Algorithms
Allan Borodin, Joan Boyar, Kim S. Larsen +1
The priority model of "greedy-like" algorithms was introduced by Borodin, Nielsen, and Rackoff in 2002. We augment this model by allowing priority algorithms to have access to advi…
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.…