5 papers · 1 filter
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…
Submodular Maximization over a Matroid -Intersection: Multiplicative Improvement over Greedy
Moran Feldman, Justin Ward
We study the problem of maximizing a non-negative monotone submodular objective subject to the intersection of arbitrary matroid constraints. The natural greedy algorithm g…
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…
Bicriteria Submodular Maximization
Moran Feldman, Alan Kuhnle
Submodular functions and their optimization have found applications in diverse settings ranging from machine learning and data mining to game theory and economics. In this work, we…
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…