Quasi M-convex and L-convex functions - quasiconvexity in discrete optimization

被引：11

作者：

Murota, K

Shioura, A ^{[1
]}

机构：

[1] Tohoku Univ, Grad Sch Informat Sci, Sendai, Miyagi 9808579, Japan

[2] Univ Tokyo, Grad Sch Informat Sci & Technol, Tokyo 1138656, Japan

来源：

DISCRETE APPLIED MATHEMATICS | 2003年 / 131卷 / 02期

关键词：

quasiconvex function; discrete optimization; matroid; base polyhedron;

D O I：

10.1016/S0166-218X(02)00468-7

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We introduce two classes of discrete quasiconvex functions, called quasi M- and L-convex functions, by generalizing the concepts of M- and L-convexity due to Murota (Adv. Math. 124 (1996) 272) and (Math. Programming 83 (1998) 313). We investigate the structure of quasi Mand L-convex functions with respect to level sets, and show that various greedy algorithms work for the minimization of quasi M- and L-convex functions. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：467 / 494

页数：28