Algorithms in Discrete Convex Analysis

Kazuo MUROTA  

IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.3   pp.344-352
Publication Date: 2000/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Algorithms for Matroids and Related Discrete Systems
discrete convex analysis,  matroid,  L-convex function,  M-convex function,  

Full Text: PDF(299.7KB)>>
Buy this Article

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 matroid-theoretic concepts, in particular, submodular functions and exchange axioms.