7 papers
Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
Niv Buchbinder, Moran Feldman, Siyue Liu +1
We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid -parity, -exch…
Load Balancing with Duration Predictions
Yossi Azar, Niv Buchbinder, Tomer Epshtein
We study the classic fully dynamic load balancing problem on unrelated machines where jobs arrive and depart over time and the goal is minimizing the maximum load, or more generall…
Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
Niv Buchbinder, Joseph, Naor +1
We introduce the \emph{submodular objectives chasing problem}, which generalizes many natural and previously-studied problems: a sequence of constrained submodular maximization pro…
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…
Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
Niv Buchbinder, Moran Feldman
We study the problem of maximizing a monotone submodular function subject to a matroid constraint, and present for it a deterministic non-oblivious local search algorithm that has…
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…