Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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…
cs.DS2026
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…