research
∙
06/30/2023
An Improved Deterministic Algorithm for the Online Min-Sum Set Cover Problem
We study the online variant of the Min-Sum Set Cover (MSSC) problem, a g...
share
research
∙
05/02/2023
A Subquadratic Bound for Online Bisection
In the online bisection problem one has to maintain a partition of n ele...
research
∙
09/11/2022
An Improved Algorithm For Online Reranking
We study a fundamental model of online preference aggregation, where an ...
research
∙
09/05/2022
Online B-Matchings for Reconfigurable Datacenters: The Power of Randomization
This paper studies the problem of how to dynamically optimize the topolo...
research
∙
04/22/2022
Deterministic Self-Adjusting Tree Networks Using Rotor Walks
We revisit the design of self-adjusting single-source tree networks. The...
research
∙
10/28/2021
Online Facility Location with Linear Delay
We study the problem of online facility location with delay. In this pro...
research
∙
02/13/2021
Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times
We present a unified framework for minimizing average completion time fo...
research
∙
07/14/2020
A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
In the online non-metric variant of the facility location problem, there...
research
∙
06/18/2020
A Competitive B-Matching Algorithm for Reconfigurable Datacenter Networks
This paper initiates the study of online algorithms for the maintaining ...
research
∙
02/11/2020
An Optimal Algorithm for Online Multiple Knapsack
In the online multiple knapsack problem, an algorithm faces a stream of ...
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
∙
11/22/2018
Better Bounds for Online Line Chasing
We study online competitive algorithms for the line chasing problem in E...
research
∙
10/01/2018
Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics
The generalized k-server problem is an extension of the weighted k-serve...
research
∙
04/22/2018