A Steepest Descent Algorithm for M-Convex Functions on Jump Systems

Kazuo MUROTA  Ken'ichiro TANAKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.5   pp.1160-1165
Publication Date: 2006/05/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.5.1160
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
jump system,  discrete convex function,  local optimality,  steepest descent algorithm,  

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

The concept of M-convex functions has recently been generalized for functions defined on constant-parity jump systems. The b-matching problem and its generalization provide canonical examples of M-convex functions on jump systems. In this paper, we propose a steepest descent algorithm for minimizing an M-convex function on a constant-parity jump system.