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

DOI10.1007/BF02592218MaRDI QIDQ3322709zbMATH OpenFDO

Authors 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) 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)

Recommendations

• scientific article; zbMATH DE number 3912107
• Submodular systems and related topics
• scientific article; zbMATH DE number 3904328
• Submodular functions and optimization
• scientific article; zbMATH DE number 4099306

Cites work

• scientific article; zbMATH DE number 3323651 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A NOTE ON SUBMODULAR FUNCTIONS ON DISTRIBUTIVE LATTICES
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• An Algorithm for Submodular Functions on Graphs
• Convex Analysis
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Minimizing a Submodular Function on a Lattice
• Rado's theorem for polymatroids
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(21)

• Recent developments in discrete convex analysis
• Critical duality
• Extensions of functions of 0-1 variables and applications to combinatorial optimization
• The Lovász extension of market games
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• Directed submodularity, ditroids and directed submodular flows
• A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors
• Are dualities appropriate for duality theories in optimization?
• \(M\)-convex functions and tree metrics
• scientific article; zbMATH DE number 3912107 (Why is no real title available?)
• Discrete Fenchel duality for a pair of integrally convex and separable convex functions
• Improved randomized algorithm for \(k\)-submodular function maximization
• On the complexity of submodular function minimisation on diamonds
• On the subdifferential of a submodular function
• Dualities between complete lattices
• Discrete convex analysis
• Convexity and Steinitz's exchange property
• Submodular function minimization
• Fenchel-type duality for matroid valuations
• A note on submodular set cover on matroids
• Recent progress on integrally convex functions

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)