Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem |
| |
Institution: | Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan |
| |
Abstract: | M-convex functions, introduced by Murota (Adv. Math. 124 (1996) 272; Math. Prog. 83 (1998) 313), enjoy various desirable properties as “discrete convex functions.” In this paper, we propose two new polynomial-time scaling algorithms for the minimization of an M-convex function. Both algorithms apply a scaling technique to a greedy algorithm for M-convex function minimization, and run as fast as the previous minimization algorithms. We also specialize our scaling algorithms for the resource allocation problem which is a special case of M-convex function minimization. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|