48 citations · 282 across the 41 of their papers we have counts for
6 papers · 1 filter
Unconstrained Submodular Maximization with Constant Adaptive Complexity
Lin Chen, Moran Feldman, Amin Karbasi
In this paper, we consider the unconstrained submodular maximization problem. We propose the first algorithm for this problem that achieves a tight -approximatio…
Guess Free Maximization of Submodular and Linear Sums
Moran Feldman
We consider the problem of maximizing the sum of a monotone submodular function and a linear function subject to a general solvable polytope constraint. Recently, Sviridenko et al.…
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…
Submodularity on Hypergraphs: From Sets to Sequences
Marko Mitrovic, Moran Feldman, Andreas Krause +1
In a nutshell, submodular functions encode an intuitive notion of diminishing returns. As a result, submodularity appears in many important machine learning tasks such as feature s…
Do Less, Get More: Streaming Submodular Maximization with Subsampling
Moran Feldman, Amin Karbasi, Ehsan Kazemi
In this paper, we develop the first one-pass streaming algorithm for submodular maximization that does not evaluate the entire stream even once. By carefully subsampling each eleme…