Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
DOI10.1007/BF02592218zbMATH Open0537.49005MaRDI QIDQ3322709FDOQ3322709
Authors: Satoru Fujishige 
Publication date: 1984
Published in: Mathematical Programming (Search for Journal in Brave)
Recommendations
subgradientKarush-Kuhn-Tucker conditionFenchel- type min-max theoremsubmodular/supermodular functions
Nonlinear programming (90C30) Optimality conditions for problems in abstract spaces (49K27) Optimality conditions for minimax problems (49K35) Abstract differentiation theory, differentiation of set functions (28A15) Duality theory (optimization) (49N15) Distributive lattices (06D99)
Cites Work
- Convex Analysis
- Title not available (Why is that?)
- The ellipsoid method and its consequences in combinatorial optimization
- Minimizing a Submodular Function on a Lattice
- Title not available (Why is that?)
- ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
- A NOTE ON SUBMODULAR FUNCTIONS ON DISTRIBUTIVE LATTICES
- Rado's theorem for polymatroids
- Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
- An Algorithm for Submodular Functions on Graphs
Cited In (21)
- \(M\)-convex functions and tree metrics
- Submodular function minimization
- Convexity and Steinitz's exchange property
- Directed submodularity, ditroids and directed submodular flows
- Are dualities appropriate for duality theories in optimization?
- Fenchel-type duality for matroid valuations
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- Discrete Fenchel duality for a pair of integrally convex and separable convex functions
- Improved randomized algorithm for \(k\)-submodular function maximization
- Critical duality
- Recent progress on integrally convex functions
- Discrete convex analysis
- A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors
- On the subdifferential of a submodular function
- Extensions of functions of 0-1 variables and applications to combinatorial optimization
- Title not available (Why is that?)
- Dualities between complete lattices
- Recent developments in discrete convex analysis
- The Lovász extension of market games
- On the complexity of submodular function minimisation on diamonds
- A note on submodular set cover on matroids
This page was built for publication: Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3322709)
