Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract)

By Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz. 2011

51 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, methodology): “[47] showed that even nonmonotone submodular functions can be approximately maximized in polynomial time using a local search algorithm, and a growing body of research has focused on extending this result in a variety of ways [25, 48, 49, 56, 90, 153].”
Fast algorithms for maximizing submodular functions (2014, methodology): “) Let us mention some other recent advances and their limitations in terms of running time: • The notion of multilinear relaxation has been used to achieve an optimal (1−1/e)-approximation for submodular maximization subject to a matroid constraint [2], as well as improved approximations for more ge”
Online Submodular Maximization with Preemption (2015, background): “[27] Moran Feldman, Joseph (Seffi) Naor, and Roy Schwartz.”
A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, background): “Lately, this approach has been extended to include both nonmonotone submodular objective functions [16], [19], [21], [48] and additional constraint sets I [37] (e.”
Near-Optimal MAP Inference for Determinantal Point Processes (2012, methodology): “Continuous methods [21, 22] use a multilinear extension of the submodular set function to the convex hull of the feasible sets and then round fractional solutions obtained by maximizing in the interior of the polytope.”
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (2012, unknown): “[12] observed that if the simulated annealing algorithm of [14] outputs a relatively poor solution, then it must generate at some point a set S which is structurally similar to some optimal solution.”