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

subgradientKarush-Kuhn-Tucker conditionFenchel- type min-max theoremsubmodular/supermodular functions

Mathematics Subject Classification ID

Nonlinear programming (90C30) Duality theory (optimization) (49N15) Optimality conditions for minimax problems (49K35) Optimality conditions for problems in abstract spaces (49K27) Abstract differentiation theory, differentiation of set functions (28A15) Distributive lattices (06D99)

Related Items

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

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