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

我们研究的实用性和适用性的算法的最小范数点问题的多面体的次模函数极小化问题，这是一个基本的问题，在组合优化问题的次模结构。实验结果表明，该算法具有良好的性能和实用性.然而，我们仍然有一定的技术计算问题的算法，这是留给未来的研究。此外，我们还提出了组合船体的概念，它是凸船体概念的推广。这为发展一种新的方法以一种纯组合的方式解决次模函数极小化问题提供了基础。我们在这个方向上取得了进展。此外，我们开发了一种用于寻找网络中最大平均割的缩放技术，这是最小费用流问题算法中的一个重要组成部分。该方法可以推广到最小费用流问题的推广--次模块流问题，并给出了一种新的多项式时间内有效的算法。此外，通过两年的调查研究，我们从次模块和超级模块系统的角度研究了具有次模块结构的组合优化问题，涉及：基多面体，贪婪算法，交叉族，广义多拟阵，新流，次模流，独立流，多拟阵流，次模分析，次模程序，字典序最优基，具有次模约束的资源分配问题等，给出了这些问题的统一解法，其结果将作为专著出版。此外，在这项调查研究的过程中，我们发现了一个错误的双截断算法最近提出的弗兰克和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.