50 citations · 69 across the 3 of their papers we have counts for
4 papers
Online Computation with Untrusted Advice
Spyros Angelopoulos, Christoph Dürr, Shendan Jin +2
We study a generalization of the advice complexity model of online computation in which the advice is provided by an untrusted source. Our objective is to quantify the impact of un…
Stochastic dominance and the bijective ratio of online algorithms
Spyros Angelopoulos, Marc P. Renault, Pascal Schweitzer
Stochastic dominance is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. A…
On the Power of Advice and Randomization for Online Bipartite Matching
Christoph Dürr, Christian Konrad, Marc Renault
While randomized online algorithms have access to a sequence of uniform random bits, deterministic online algorithms with advice have access to a sequence of advice bits, i.e., bit…
Online Algorithms with Advice for Bin Packing and Scheduling Problems
Marc P. Renault, Adi Rosén, Rob van Stee
We consider the setting of online computation with advice, and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these prob…