research
∙
04/04/2023
Mixing predictions for online metric algorithms
A major technique in learning-augmented online algorithms is combining m...
share
research
∙
11/10/2022
The Randomized k-Server Conjecture is False!
We prove a few new lower bounds on the randomized competitive ratio for ...
research
∙
02/09/2022
Shortest Paths without a Map, but with an Entropic Regularizer
In a 1989 paper titled "shortest paths without a map", Papadimitriou and...
research
∙
11/30/2021
Online metric allocation
We introduce a natural online allocation problem that connects several o...
research
∙
10/25/2021
Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
We study the online problem of minimizing power consumption in systems w...
research
∙
02/20/2021
Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle
The k-server conjecture, first posed by Manasse, McGeoch and Sleator in ...
research
∙
11/18/2020
Scale-Free Allocation, Amortized Convexity, and Myopic Weighted Paging
Inspired by Belady's optimal algorithm for unweighted paging, we conside...
research
∙
09/17/2020
Metrical Service Systems with Transformations
We consider a generalization of the fundamental online metrical service ...
research
∙
03/04/2020
Online metric algorithms with untrusted predictions
Machine-learned predictors, although achieving very good results for inp...
research
∙
11/05/2019
Unbounded lower bound for k-server against weak adversaries
We study the resource augmented version of the k-server problem, also kn...
research
∙
06/10/2019
Pure entropic regularization for metrical task systems
We show that on every n-point HST metric, there is a randomized online a...
research
∙
11/22/2018
Better Bounds for Online Line Chasing
We study online competitive algorithms for the line chasing problem in E...
research
∙
07/17/2018