Fundamental Studies on Large-Scale combinatorial Systems Based on Submodular Analysis

点击翻译按钮获取中文摘要

We have investigated the following three based on the submodular analysis for large-scale combinatorial systems.(1) The structures of combinatorial polyhedra determined by submodular functions and bisubmodular function,(2) network optimization problems related to flows and cuts,(3) algorithms for the minimun-norm point problem that gives us practical algorithms for minimizing submodular functions, basic tools in submodular analysis.Concerning (1), we derived an algorithm for discerning whether a given crossing-submodular function defines a nonempty base polyhedron, and proposed new algorithms for solving the intersection problem of two submodular systems. Moreover, we examined the structures of combinatorial polyhedra determined byu bisubmodular functions and gave a greedy algorithm for minimizing separable convex functions over the polyhedra. We also revealed the relationship between bisubmodular functions and bidirected flows.Concerning (2), we developed an efficient algorithm for finding a maximum mean cut and invented a new method, called a speculative contraction method, for minimum-cost flows. The effectiveness of these algorithms were shown by computational experiments.For (3), we gave algorithms for finding a nearest pair of points in two polyhedra and for finding the minimum-norm point in the intersection of a polyhedron and a hyperplane, and showed their applicability for large-scale problems.