4 papers
Primal-Dual Online Algorithms for the Parking Permit Problem
Christian Coester, Alex Turoczy
The Parking Permit Problem (PPP), first studied by Meyerson, is a classic online problem generalizing the ski rental problem. We re-examine the PPP using the primal-dual scheme, ob…
Learning-Augmented Online Minimization with Dual Predictions
Christian Coester, Alexa Tudose, Alexander Turoczy
We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theo…
Randomized -server in polynomial time
Christian Coester, Romain Cosson
We study the design of computationally efficient randomized algorithms for the -server problem. Existing randomized algorithms with the best known competitive ratios are, on the…
Transposition is Nearly Optimal for IID List Update
Christian Coester
The list update problem is one of the oldest and simplest problems in online algorithms: A set of items must be maintained in a list while requests to these items arrive over time.…