4 papers
Multi-Level Aggregation via Dual Fitting: An -Competitive Algorithm
Sara Ahmadian, Shuchi Chawla, Ravi Kumar +2
We present a new online algorithm for the well-known Multi-Level Aggregation Problem (MLAP) with arbitrary delay functions, achieving a -competitive ratio, where is the dep…
Stochastic Caching via Subset Entropy
Ravi Kumar, Roie Levin, Joseph +2
A classic approach to beyond worst-case algorithm design is to impose stochastic assumptions on the input. However, a limiting feature of stochastic analyses is that, by the min-ma…
Sketching Intersection Profiles: A Simple Proof and Three Applications
Flavio Chierichetti, Mirko Giacchini, Ravi Kumar +3
In this work we settle the complexity of three sketching problems. (i) We show that sketching vertex neighborhood sizes in graphs requires bits, standing in sharp contras…
Adaptive Weighted Averaging
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar +1
We study the problem of selecting the largest among unknown values given only a single unbiased estimate for each . We design strategies that are sim…