A capacity scaling algorithm for M-convex submodular flow |
| |
Authors: | Satoru Iwata Satoko Moriguchi Kazuo Murota |
| |
Institution: | (1) Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-8656, Japan;(2) CREST, Japan Science and Technology Agency, Saitama 332-0012, Japan;(3) Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-8656, Japan;(4) PRESTO JST, |
| |
Abstract: | This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum submodular flow problems.Mathematics Subject Classification (1991): 90C27A preliminary version of this paper has appeared in Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization (IPCO X), LNCS 3064, Springer-Verlag, 2004, pp. 352–367. |
| |
Keywords: | Discrete optimization Discrete convex function Submodular flow Algorithm |
本文献已被 SpringerLink 等数据库收录! |
|