Basic Studies on Submodular Structure of Large-scale Combinatorial Systems

本课题最重要的成果是用于最小化子模函数的组合、强多项式时间算法。自1981年以来，如何获得这样的组合算法一直是一个长期悬而未决的问题。利用该算法，我们可以构造有效的算法来解决许多组合优化问题，如子模流问题，现有的算法都假定了子模函数最小化的oracle。此外，我们得到了以下结果。我们简短地证明了M. Queyranne算法对于最小化对称子模函数的有效性。提出了一种利用参数最大流算法求解凹函数产生的子模函数的最小化算法。我们还证明了正模函数的层次性，它推广了对称次模函数。进一步证明了Faigle和Kern研究的对偶贪心多面体属于次模流多面体。针对子模函数最小化的最小范数点问题，提出了一种在点的凸包与仿射空间的交点上求最小范数点的有效算法。

The most important result of this project is the combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. It has been a long-standing open problem to obtain such a combinatorial algorithm since 1981. With the aid of this algorithm we can construct efficient algorithms for a lot of combinatorial optimization problems such as the submodular flow problem for which existing algorithms assume the oracle for submodular function minimization.Moreover, we have obtained the following results. We gave a short proof of the validity of M. Queyranne's algorithm for minimizing symmetric submodular functions. We proposed an algorithm for minimizing submodular functions arising from concave functions by means of parametric max-flow algorithms. We also showed the laminarity property of posi-modular functions, which generalize symmetric submodular functions. Furthermore, we proved that the dual greedy polyhedra investigated by Faigle and Kern belong to the class of submodular flow polyhedra. Concerning the minimum-norm point problem, related to submodular function minimization, we proposed an efficient algorithm for finding the minimum-norm point in the intersection of the convex hull of points and an affine space.