Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem

摘要

M-convex functions, introduced by Murota (1996, 1998), 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.