7 papers
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…
The Online Submodular Cover Problem
Anupam Gupta, Roie Levin
In the submodular cover problem, we are given a monotone submodular function , and we want to pick the min-cost set such that . Motivated by problems in network…
Fully-Dynamic Submodular Cover with Bounded Recourse
Anupam Gupta, Roie Levin
In submodular covering problems, we are given a monotone, nonnegative submodular function and wish to find the min-cost set such tha…
Competitively Consistent Clustering
Niv Buchbinder, Roie Levin, Yue Yang
In fully-dynamic consistent clustering, we are given a finite metric space , and a set of possible locations for opening centers. Data points arrive and depar…