首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号