7 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…
Online Monotone Metric Embeddings
Christian Coester, Yichen Huang
Metric embeddings into structured spaces, particularly hierarchically well-separated trees (HSTs), are a fundamental tool in the design of online algorithms. In the classical onlin…
Chasing Small Sets Optimally Against Adaptive Adversaries
Christian Coester, Alexa Tudose
We study deterministic online algorithms for the problem of chasing sets of cardinality at most in a metric space, also known as metrical service systems and equivalent to widt…
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.…