Analysis of Combinatorial Optimization Problems with Submodular Structures and Design of Efficient Algorithms
Analysis of Combinatorial Optimization Problems with Submodular Structures and Design of Efficient Algorithms
批准号:
01540168
负责人:
FUJISHIGE Satoru
金额:
$0.64万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for General Scientific Research (C)
财政年份:
1989
资助国家:
日本
项目状态:
已结题
起止时间:
1989 至 1990
中文摘要
我们考察了多面体上最小范点问题的算法对子模函数最小化问题的实用性和适用性,子模函数最小化问题是具有子模结构的组合优化问题中的一个基本问题。计算实验表明,该算法具有良好的性能和实用性。然而,关于该算法,我们还存在一定的技术计算问题,有待进一步研究。此外,我们还提出了组合壳的概念,它是凸壳概念的推广。这为发展以纯组合方式解子模函数极小化问题的新方法提供了基础。我们正朝着这个方向取得进展。此外,我们还开发了一种标度技术来寻找网络中的最大平均割,这是最小费用流问题算法中的一个重要组成部分。通过两年的研究,从子模系统和超模系统的角度,研究了基多面体、贪婪算法、交叉族、广义多面体、新流、子模流、独立流、多面体流、子模分析、子模程序、词典最优基、带子模约束的资源分配问题等具有子模结构的组合优化问题,给出了这些问题的统一方法,并将结果以专著形式发表。在调查研究的过程中,我们发现了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.
期刊论文(13)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
Kazuo Iwano: "A New Scaling Algorithm for the Maximum Mean Cut Problem" Algorithmica.
Kazuo Iwano:“最大均值割问题的新缩放算法”Algorithmica。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Takeshi MAITOH: "A note on the Frank-Tardos bi-truncation algorithm for crossing submodular functions" Mathematical Programming.
Takeshi MAITOH:“关于用于交叉子模函数的 Frank-Tardos 双截断算法的注释”数学编程。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
K. Iwano, S. Misono, S. Tezuka and S. Fujishige: "A new scaling algorithm for the maximum mean cut problem" Algorithmica.
K. Iwano、S. Misono、S. Tezuka 和 S. Fujishige:“最大平均切割问题的新缩放算法”Algorithmica。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
S. Fujishige and P. Zhan: "A dual algorithm for finding the minimum-norm point in a polytope" Journal of the Operations Research Society of Japan. 33. 188-195 (1990)
S. Fujishige 和 P. Zhan:“在多胞体中寻找最小范数点的双重算法”,日本运筹学会杂志。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Satoru FUJISHIGE: "Submodular Functions and Optimization" North-Holland, 270 (1991)
Satoru FUJISHIGE:“子模函数和优化” North-Holland,270 (1991)
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
共 13 条
Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures
-
批准号:20310088
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$12.56万
-
财政年份:2008
-
负责人:FUJISHIGE Satoru
-
依托单位:
Analysis of Large-scale Discrete Optimization Problems and Development of Efficient Algorithms Based on Submodularity Structures
-
批准号:16310111
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$10.44万
-
财政年份:2004
-
负责人:FUJISHIGE Satoru
-
依托单位:
Fundamental Research on Fast Algorithms for Large-Scale Discrete Optimization Problems Based on Submodularity Structures
-
批准号:13480113
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$4.61万
-
财政年份:2001
-
负责人:FUJISHIGE Satoru
-
依托单位:
Basic Studies on Submodular Structure of Large-scale Combinatorial Systems
-
批准号:10680429
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.11万
-
财政年份:1998
-
负责人:FUJISHIGE Satoru
-
依托单位:
Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures
-
批准号:10205217
-
项目类别:Grant-in-Aid for Scientific Research on Priority Areas (B)
-
资助金额:$11.2万
-
财政年份:1998
-
负责人:FUJISHIGE Satoru
-
依托单位:
Fundamental Studies on Large-Scale combinatorial Systems Based on Submodular Analysis
-
批准号:04832006
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$1.28万
-
财政年份:1992
-
负责人:FUJISHIGE Satoru
-
依托单位:
海外基金