权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

子模结构组合优化问题分析及高效算法设计

基本信息

批准号：
01540168
负责人：
FUJISHIGE Satoru
金额：
$ 0.64万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1989
资助国家：
日本
起止时间：
1989 至 1990
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-01540168/
关键词：
Submodular Functions Combinatorial Optimization Algorithms 離散システム数理計画

项目摘要

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.

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