Submodular Functions, Matroids, and Certain Polyhedra

By J. Edmonds. Combinatorial Optimization, 2001

1,364 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/4416e09f9ab450ad16f655d1ccbf79ef1f0a7da1

How researchers see this paper

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

In Computational Theory and Mathematics

Citations in the corpus

A Joint Location - Inventory Model (2003, background): “Later, Edmonds (1970) renewed attention to submodular functions by proving the integrality of polymatroids, which are polytopes that arise from rational submodular functions. Edmonds’ results generalized many well-known theorems about integral polytopes. Submodular function minimization is the follo”
Designing Random Allocation Mechanisms: Theory and Applications (2013, background): “The total unimodularity of matrix M in turn follows from Edmonds (1970). A fuller self-contained proof is available in Web Appendix C.”
Matroid Theory for Algebraic Geometers (2014, methodology): “Edmonds studied the structure of independence polytope and was able to prove the following important theorem in combinatorial optimization: Theorem 8.1.”
Discrete Polymatroids (2002, background): “How can we find the vertices of a polymatroid? A complete answer was obtained by Edmonds [5].”
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, methodology): “The following fundamental lemma easily follows from a theorem of Edmonds [4] on the vector reduction of polymatroids (see [12, Corollaries 3.4 and 3.5]).”
Valuative invariants for polymatroids (2009, methodology): “In this paper we construct the Z-modules of all Z-valued valuative functions for labeled matroids and polymatroids on a fixed ground set, and their unlabeled counterparts, the Z-modules of valuative invariants.”
Hopf Algebras in Combinatorics (2014, background): “A basic result about matroids, due to Edmonds [59], describes the edges in the matroid base polytope which is the convex hull of all vectors {b∈B ǫb}B∈B(M) inside R with standard basis {ǫe}e∈E .”
Stellahedral geometry of matroids (2022, methodology): “Applying a criterion for base-point-freeness [CLS11, Theorem 6.4.9] to the stellahedral fan along with Corollary 3.14, one has that O 𝑋 𝐸 ( 𝐷 ) is base-point-free if and only if the following two conditions are satisﬁed: (1) For 𝑖 ∈ 𝐸 and a subset 𝑆 (cid:2) 𝐸 not containing i , one has…”
Discrete convex analysis: A tool for economics and game theory (2016, background): “…is adapted to discrete settings and the mathematical results in matroid/submodular function theory are generalized.1 The theory extends the direction set forth in discrete optimization by Edmonds (1970), Frank (1982), Fujishige (1984), and Lovász (1983); see also Fujishige (2005, Chapter VII).”
Information Inequalities for Joint Distributions, With Interpretations and Applications (2008, background): “of functions has been intensely studied ever since the pioneering work of Edmonds [13], who used them to define polymatroids.”