9 papers
Competitive Online Clustering with Movement Cost
Christian Coester, Yichen Huang, Michael Mitzenmacher
We study the problem of online clustering with movement cost, which generalizes the fundamental -server problem. At each time step, the algorithm is given a set of points in a m…
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.…
Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
Xingjian Bai, Christian Coester, Romain Cosson
Introduced by Papadimitriou and Yannakakis in 1989, layered graph traversal is a central problem in online algorithms and mobile computing that has been studied for several decades…
Sorting with Predictions
Xingjian Bai, Christian Coester
We explore the fundamental problem of sorting through the lens of learning-augmented algorithms, where algorithms can leverage possibly erroneous predictions to improve their effic…