12 papers · 1 filter
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…
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…
Competitive Bundle Trading
Yossi Azar, Niv Buchbinder, Roie Levin +1
A retailer is purchasing goods in bundles from suppliers and then selling these goods in bundles to customers; her goal is to maximize profit, which is the revenue obtained from se…