Algorithms in discrete convex analysis
Kazuo Murota · 2000
This is a survey of algorithmic results in the theory of "discrete convex analysis" for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, the Fenchel min-max duality, and separation theorems. The technical development is based on matroidtheoretic concepts, in particular, submodular functions and exchange axioms. Keywords: discrete convex analysis, matroid, L-convex function, M-convex function 1 Introduction In the field of nonlinear programming (in continuous variables) convex analysis plays a pivotal role both in theory and in practice (e.g., [36]). An analogous theory for discrete optimization (nonlinear integer programming), called "discrete convex analysis," has been advocated by the author [29, 30]. The theory is developed by adapting the ideas in convex analysis and generalizing the results in matroid theory. Symbolically, Discrete Convex Anal...