18 papers
Dynamic Contention Resolution Schemes
Moran Feldman, Gregory Kehne, Roie Levin +1
We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs). These are dynamic analogs…
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…
An Information-Theoretic Lower Bound for Randomized Online Set Cover
Roie Levin
We show an information-theoretic lower bound of for online set cover against randomized algorithms, for all sufficie…
Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems
Joseph Koutsoutis, Jesse Lerner, Roie Levin +1
We give a new approximation algorithm for Node Weighted Steiner Tree and Node Weighted Steiner Forest. Our algorithm matches the bounds of Klein & Ravi [J. Algorithms '…
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…
Trading Prophets with Initial Capital
Yossi Azar, Niv Buchbinder, Roie Levin +1
Correa et al. [EC' 2023] introduced the following trading prophets problem. A trader observes a sequence of stochastic prices for a stock, each drawn from a known distribution, and…