Scaling Algorithms for M-convex Function Minimization
Satoko Moriguchi, Kazuo Murota, Akiyoshi Shioura · 2001
M-convex functions have various desirable properties as convexity in discrete optimization. We can find a global minimum of an M-convex function by a greedy algorithm, i.e., so-called descent algorithms work for the minimization. In this paper, we apply a scaling technique to a greedy algorithm and propose an efficient algorithm for the minimization of an M-convex function. Computational results are also reported.