3 citations · 3 across the 6 of their papers we have counts for
15 papers · 1 filter
The -server conjecture is true
Christian Coester, Elias Koutsoupias, Marek Zbysiński
The -server conjecture states that a deterministic online algorithm can achieve competitive ratio on every metric space. We prove the conjecture. Specifically, we show that…
Online 3-Taxi on General Metrics
Christian Coester, Tze-Yang Poon
The online -taxi problem, introduced in 1990 by Fiat, Rabani and Ravid, is a generalization of the -server problem where taxis must serve a sequence of requests in a metr…
Smoothed Analysis of Online Metric Problems
Christian Coester, Jack Umenberger
We study three classical online problems -- -server, -taxi, and chasing size sets -- through a lens of smoothed analysis. Our setting allows request locations to be adver…
Learning-Augmented Priority Queues
Ziyad Benomar, Christian Coester
Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is to efficiently support the insertion of new elements…
Competitive Algorithms for Block-Aware Caching
Christian Coester, Roie Levin, Joseph +2
We study the block-aware caching problem, a generalization of classic caching in which fetching (or evicting) pages from the same block incurs the same cost as fetching (or evictin…
Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
Antonios Antoniadis, Christian Coester, Marek Eliáš +2
We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between…