A Unified Continuous Greedy Algorithm for Submodular Maximization

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

294 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

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

In Computer Networks and Communications

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].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “The multi-linear extension is neither convex nor concave but has marginal convexity properties that may be used for the design and analysis of algorithms for maximization problems [42, 68].”
Fast algorithms for maximizing submodular functions (2014, background): “Extensions and generalizations to nonmonotone submodular functions have been developed in [7, 25, 34, 26, 16, 13, 9, 10, 3, 1].”
Submodular Maximization with Cardinality Constraints (2014, methodology): “004 should be considered as a “proof of concept” that the natural 1/e−o(1) guarantee of [20] is not the right answer.”
Near-Optimal MAP Inference for Determinantal Point Processes (2012, methodology): “When the objective f(Y ) is a submodular set function, as in our setting, the multilinear extension can be used to obtain certain theoretical guarantees for the relaxed optimization scheme described above [21, 25].”
Submodular function maximization via the multilinear relaxation and contention resolution schemes (2011, methodology): “For conciseness, and in view of the recent results in [24], we do not include this third algorithm in this paper, and concentrate on the first two algorithms mentioned in the prec eding paragraph, which allow us to demonstrate the main new algorithmic insights.”
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (2012, unknown): “Both problems are already known to have a tight approximation [13].”
Optimal approximation for submodular and supermodular optimization with bounded curvature (2013, background): “The multilinear extension F satisfies the following properties, which follow from the submodularity of f [6, 18]: 1.”
The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “…Tang et al. [75]), quantum physics (see, e.g., Gilbert [41], Designolle et al. [30]), submodular function maximization (see, e.g., Feldman et al. [33], Vondrák [79], Badanidiyuru and Vondrák [5], Mirzasoleiman et al. [60], Hassani et al. [45], Mokhtari et al. [61], Anari et al. [1], Anari et al.…”