Submodular functions and convexity

By L. Lov'asz. 1982

How researchers see this paper

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

Citations in the corpus

Causal Markov condition for submodular information measures (2010, background): “Note that submodular functions have been considered in different contexts, see for example (Lovász, 1983; Matus, 1994; Madiman & Tetali, 2008).”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “The next proposition draws precise links between convexity and submodularity, by showing that a set-function F is submodular if and only if its Lovász extension f is convex [135].”
Non-monotone submodular maximization under matroid and knapsack constraints (2009, background): “Optimizing submodular functions is a central subject in operations research and combinatorial optimization [36].”
Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints (2013, background): “While general set function optimization is often intractable, many forms of submodular function optimization can be solved near optimally or even optimally in certain cases, and hence submodularity is also often called the discrete analog of convexity [34].”
A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid (2008, background): “Lovász (1983) discovered this formula by considering the problem of extending the domain of pseudoBoolean functions to Rn.”
Optimization for Medical Image Segmentation: Theory and Practice When Evaluating With Dice Score or Jaccard Index (2020, methodology): “As with other surrogates described in this section, the Lovász softmax first projects pixel scores into [0, 1] using a softmax operation, and then computes the Lovász extension [24] of the submodular loss function, which is convex and differentiable almost everywhere, giving it favorable properties ”
On Submodularity and Controllability in Complex Dynamical Networks (2014, background): “This is made precise by the following result from [27], which will be useful for verifying submodularity of set functions later.”
Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract) (2011, background): “The other known extension of submodular functions is the Lovász extension introduced in [13].”
A Joint Location - Inventory Model (2003, background): “We begin with some elementary properties of submodular functions, the proofs of which are straightforward (See, for example, Lovasz 1982 or Fugishige 1991).”
Multi-document Summarization via Budgeted Maximization of Submodular Functions (2010, background): “(Lovasz, 1983) if for any S, T ⊆ V , we have”
Restricted Strong Convexity Implies Weak Submodularity (2016, background): “For example, the convex closure of a submodular function can be tractably computed as its Lovász extension [33].”
A Linear Programming Approach to Max-Sum Problem: A Review (2007, background): “(Super-) submodularity, for bivariate functions also known as (inverse) Monge property [62], is well-known to simplify many optimization tasks; in fact, it can be considered a discrete counterpart of convexity [63].”
Submodular function maximization via the multilinear relaxation and contention resolution schemes (2011, background): “The best-studied extension of a submodular function is the L ovász extension [39]; however, being a convex function, it is mostly suitable for submodular function minimiz ation problems.”
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization (2013, methodology): “This follows since linear optimization over such a submodular polyhedron domain is efficient, by an O(n log n) time greedy algorithm (Edmonds, 1970; Lovász, 1983; Bach, 2011).”
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions (2000, background): “There are also close connections between submodularity and convexity [12, 21 ].”