23 citations · 48 across the 24 of their papers we have counts for
27 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…
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…
Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
Niv Buchbinder, Moran Feldman
Maximization of submodular functions under various constraints is a fundamental problem that has been studied extensively. A powerful technique that has emerged and has been shown…
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…
Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
Niv Buchbinder, Moran Feldman
Submodular maximization under various constraints is a fundamental problem studied continuously, in both computer science and operations research, since the late 's. A centra…
Maintaining Matroid Intersections Online
Niv Buchbinder, Anupam Gupta, Daniel Hathcock +2
Maintaining a maximum bipartite matching online while minimizing recourse/augmentations is a well studied problem, motivated by content delivery, job scheduling, and hashing. A bre…
Chasing Positive Bodies
Sayan Bhattacharya, Niv Buchbinder, Roie Levin +1
We study the problem of chasing positive bodies in : given a sequence of bodies revealed online…
Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)
Niv Buchbinder, Joseph, Naor +1
For numerous online bipartite matching problems, such as edge-weighted matching and matching under two-sided vertex arrivals, the state-of-the-art fractional algorithms outperform…
Fair Coin Flipping: Tighter Analysis and the Many-Party Case
Niv Buchbinder, Iftach Haitner, Nissan Levi +1
In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some adversarial parties try to bias the output. In this work we focus…
Online -Taxi via Double Coverage and Time-Reverse Primal-Dual
Niv Buchbinder, Christian Coester, Joseph +1
We consider the online -taxi problem, a generalization of the -server problem, in which servers are located in a metric space. A sequence of requests is revealed one by o…
Online Virtual Machine Allocation with Predictions
Niv Buchbinder, Yaron Fairstein, Konstantina Mellou +3
The cloud computing industry has grown rapidly over the last decade, and with this growth there is a significant increase in demand for compute resources. Demand is manifested in t…
Metrical Service Systems with Transformations
Sébastien Bubeck, Niv Buchbinder, Christian Coester +1
We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which…
-Servers with a Smile: Online Algorithms via Projections
Niv Buchbinder, Anupam Gupta, Marco Molinaro +2
We consider the -server problem on trees and HSTs. We give an algorithm based on Bregman projections. This algorithm has a competitive ratios that match some of the recent resul…
Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid
Niv Buchbinder, Moran Feldman, Mohit Garg
We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (1/2 + ε)-approximation for th…
Online Submodular Maximization: Beating 1/2 Made Simple
Niv Buchbinder, Moran Feldman, Yuval Filmus +1
The Submodular Welfare Maximization problem (SWM) captures an important subclass of combinatorial auctions and has been studied extensively from both computational and economic per…
$O(\mbox{depth})$-Competitive Algorithm for Online Multi-level Aggregation
Niv Buchbinder, Moran Feldman, Joseph Naor +1
We consider a multi-level aggregation problem in a weighted rooted tree, studied recently by Bienkowski et al. (2015). In this problem requests arrive over time at the nodes of the…
Constrained Submodular Maximization via a Non-symmetric Technique
Niv Buchbinder, Moran Feldman
The study of combinatorial optimization problems with a submodular objective has attracted much attention in recent years. Such problems are important in both theory and practice b…
Deterministic Algorithms for Submodular Maximization Problems
Niv Buchbinder, Moran Feldman
Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function max…
Online Submodular Maximization with Preemption
Niv Buchbinder, Moran Feldman, Roy Schwartz
Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role in various disciplines. We study…
Online Packing and Covering Framework with Convex Objectives
Niv Buchbinder, Shahar Chen, Anupam Gupta +3
We consider online fractional covering problems with a convex objective, where the covering constraints arrive over time. Formally, we want to solve $\min\,\{f(x) \mid Ax\ge \mathb…