research
∙
12/06/2022
Online Min-Max Paging
Motivated by fairness requirements in communication networks, we introdu...
share
research
∙
11/08/2022
Prophet Inequality: Order selection beats random order
In the prophet inequality problem, a gambler faces a sequence of items a...
research
∙
10/19/2021
Factorial Lower Bounds for (Almost) Random Order Streams
In this paper we introduce and study the StreamingCycles problem, a rand...
research
∙
02/22/2021
The Randomized Competitive Ratio of Weighted k-server is at least Exponential
The weighted k-server problem is a natural generalization of the k-serve...
research
∙
02/18/2020
How to Solve Fair k-Center in Massive Data Models
Fueled by massive data, important decision making is being automated wit...
research
∙
08/14/2018
Testing Graph Clusterability: Algorithms and Lower Bounds
We consider the problem of testing graph cluster structure: given access...
research
∙
07/23/2018
Set Cover and Vertex Cover with Delay
The set cover problem is one of the most fundamental problems in compute...
research
∙
11/06/2017