Analysis of Combinatorial Optimization Problems with Submodular Structures and Design of Efficient Algorithms

将多面体上最小范数点问题的算法应用于子模结构组合优化问题中的基本问题——子模函数最小化问题，验证了该算法的实用性和适用性。计算实验表明，该算法具有良好的性能和实用性。但是，该算法还存在一定的技术计算问题，有待进一步研究。在此基础上，提出了组合船体的概念，这是对凸船体概念的推广。这为发展一种以纯组合方式求解次模函数最小化问题的新方法奠定了基础。我们正朝着这个方向取得进展。此外，我们开发了一种缩放技术，用于在网络中寻找最大平均切割，这是最小成本流问题算法的重要组成部分。该方法可以推广到次模流问题，即最小代价流问题的推广，并提供了一种新的、运行时间为多项式的高效算法。此外，通过两年的调查研究，我们从次模和超模系统的角度研究了具有次模结构的组合优化问题，涉及到：基多面体、贪心算法、交叉族、广义多拟体、新流、次模流、独立流、多拟体流、次模分析、次模程序、字典最优基、具有次模约束的资源分配问题等。我们对这些问题给出了一个统一的方法，结果将作为专著发表。此外，在这次调查研究的过程中，我们发现了Frank和Tardos最近提出的关于次模函数最小化问题的双截断算法中的一个错误，并给出了一个正确的版本。

We examined the practicality and applicability of the algorithm for the minimum norm point problem on a polytope to the submodular function minimization problem, which is a fundamental problem in combinatorial optimization problems with submodular structures. The computational experiments showed a good performance and practicality of the algorithm. However, we still have certain technical computational problem concerning the algorithm, which is left for future research. Furthermore, we proposed a concept of combinatorial hull, which is a generalization of the concept of convex hull. This gives a basis for developing a new method for solving the submodular function minimization problem in a purely combinatorial manner. We are making a progress in this direction.Also, we developed a scaling technique for finding a maximum mean cut in a network, which is an important component in algorithms for the minimum cost flow problem. This approach can be extended to the submodular flow problem, a generalization of the minimum cost flow problem, and furnishes an efficient algorithm that is new and runs in polynomial time.Moreover, through the two-year survey research, we examined, from the point of view of submodular and supermodular systems, the combinatorial optimization problems with submodular structures related to : base polyhedra, greedy algorithm, crossing families, generalized polymatroids, neoflows, submodular flows, independent flows, polymatroid flows, submodular analysis, submodular programs, lexicographically optimal bases, the resource allocation problem with submodular constraints etc. We gave a unifying approach to these problems and the results will be published as a monograph. Also, in the course of this survey research we found an error in the bi-truncation algorithm recently proposed by Frank and Tardos, related to the submodular function minimization problem, and showed a correct version of it.