Coordinatewise domain scaling algorithm for M-convex function minimization |
| |
Authors: | Akihisa Tamura |
| |
Institution: | (1) Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan |
| |
Abstract: | We present a polynomial time scaling algorithm for the minimization of an M-convex function. M-convex functions are nonlinear discrete functions with (poly)matroid structures, which are being recognized as playing a fundamental role in tractable cases of discrete optimization. The algorithm is applicable also to a variant of quasi M-convex functions.Mathematics Subject Classification (2000):90C27, 68W40, 05B35This work is supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan. |
| |
Keywords: | Discrete convex analysis M-convex function minimization Scaling algorithm |
本文献已被 SpringerLink 等数据库收录! |
|