354 citations · 566 across the 34 of their papers we have counts for
3 papers · 1 filter
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…
The expanding search ratio of a graph
Spyros Angelopoulos, Christoph Dürr, Thomas Lidbetter
We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. A sequence of edges is chosen starting from a given root vertex s…
The triangle scheduling problem
Christoph Dürr, Zdeněk Hanzálek, Christian Konrad +4
This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality lev…