Basic Studies on Submodular Structure of Large-scale Combinatorial Systems

这个项目最重要的成果是组合，强多项式时间算法最小化次模函数。自1981年以来，获得这样的组合算法一直是一个长期存在的公开问题。借助于该算法，我们可以构造出求解许多组合优化问题的有效算法，如求解子模流问题，而已有的算法都是假设子模函数极小化的预言。我们对M的有效性给出了一个简短的证明。求对称次模函数最小值的Queyranne算法。利用参数最大流算法，提出了一个极小化凹函数的次模函数的算法。证明了正模函数的层合性，推广了对称次模函数。进一步证明了Faigle和克恩研究的对偶贪婪多面体属于次模流多面体类。针对与次模函数极小化有关的最小范数点问题，提出了一种求点的凸船体与仿射空间交线上最小范数点的有效算法.

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.