Notes on L-/M-convex functions and the separation theorems

Citation
S. Fujishige et K. Murota, Notes on L-/M-convex functions and the separation theorems, MATH PROGR, 88(1), 2000, pp. 129-146
Citations number
30
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
88
Issue
1
Year of publication
2000
Pages
129 - 146
Database
ISI
SICI code
0025-5610(200006)88:1<129:NOLFAT>2.0.ZU;2-U
Abstract
The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular function and base pol yhedron, respectively, and discrete separation theorems are established for L-convex/concave functions and for M-convex/concave functions as generaliz ations of Frank's discrete separation theorem for submodular/supermodular s et functions and Edmonds' matroid intersection theorem. This paper shows th e equivalence between Murota's L-convex functions and Favati and Tardella's submodular integrally convex functions, and also gives alternative proofs of the separation theorems that provide a geometric insight by relating the m to the ordinary separation theorem in convex analysis.