Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions

DOI10.1007/BF02592218zbMath0537.49005MaRDI QIDQ3322709

Satoru Fujishige

Publication date: 1984

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

subgradient; Karush-Kuhn-Tucker condition; Fenchel- type min-max theorem; submodular/supermodular functions

Mathematics Subject Classification ID

90C30: Nonlinear programming

49N15: Duality theory (optimization)

49K35: Optimality conditions for minimax problems

49K27: Optimality conditions for problems in abstract spaces

28A15: Abstract differentiation theory, differentiation of set functions

06D99: Distributive lattices

Related Items

On the complexity of submodular function minimisation on diamonds, A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors, Are dualities appropriate for duality theories in optimization?, Submodular function minimization, A note on submodular set cover on matroids, Directed submodularity, ditroids and directed submodular flows, Fenchel-type duality for matroid valuations, Discrete convex analysis, \(M\)-convex functions and tree metrics, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Critical duality, The Lovász extension of market games, On the subdifferential of a submodular function, Extensions of functions of 0-1 variables and applications to combinatorial optimization, Dualities between complete lattices

Cites Work

• Unnamed Item
• Unnamed Item
• The ellipsoid method and its consequences in combinatorial optimization
• A NOTE ON SUBMODULAR FUNCTIONS ON DISTRIBUTIVE LATTICES
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Rado's theorem for polymatroids
• Minimizing a Submodular Function on a Lattice
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• An Algorithm for Submodular Functions on Graphs
• Convex Analysis