Notes on L-/M-convex functions and the separation theorems |
| |
Authors: | Satoru Fujishige Kazuo Murota |
| |
Institution: | (1) Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531, Japan, e-mail: fujishig@sys.es.osaka-u.ac.jp, JP;(2) Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan, e-mail: murota@kurims.kyoto-u.ac.jp, JP |
| |
Abstract: | The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular
function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions
and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set
functions and Edmonds’ matroid intersection theorem. This paper shows the 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 them to the ordinary separation theorem in convex analysis.
Received: November 27, 1997 / Accepted: December 16, 1999?Published online May 12, 2000 |
| |
Keywords: | : L-convex functions – M-convex functions – integrally convex functions – submodularity – separation theorems |
本文献已被 SpringerLink 等数据库收录! |
|