05995758

j

05995758 Moriguchi, Satoko Shioura, Akiyoshi Tsuchimura, Nobuyuki M-convex function minimization by continuous relaxation approach: proximity theorem and algorithm. SIAM J. Optim. 21, No. 3, 633-668 (2011). 2011 Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA EN discrete optimization convex function submodular function matroid

doi:10.1137/080736156

This article studies a novel algorithm for the M-convex function minimization problem in discrete optimization. The authors begin with a useful introduction to the problem and an overview of the continuous relaxation approach for its solution. This is followed by a section containing important background notation, definitions and results relating to submodular functions that are relevant to the continuous relaxation method. In the third section, the proposed algorithm for the M-convex optimization problem is presented in detail, including applications of the algorithm to the laminar convex resource allocation problem and the network resource allocation problem. The last section of the paper focuses on the lengthly proofs of the main theorems which were outlined in the previous sections. Efstratios Rappos (Aubonne)