32 citations · 43 across the 13 of their papers we have counts for
Showing 2026Show all
3 papers · 1 filter
cs.DS2026
Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness
Anish Hebbar, Ravi Kumar, Roie Levin +3
Suppose an online algorithm is given an unbiased -sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study…
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
Incremental Dominating Set
Ilan Doron Arad, Jonathan Gal, Seffi Naor
Dominating Set is a fundamental problem in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or adjacent to a selected…