Basic Studies on Submodular Structure of Large-scale Combinatorial Systems

大规模组合系统子模结构的基础研究

• 批准号: 10680429
• 负责人: FUJISHIGE Satoru
• 金额: $ 2.11万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680429/
• 关键词: Submodular functions; Combinatorial optimization; Discrete Algorithms

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.

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

项目成果

S. Fujishige and S. Iwata: "Minimizing a submodular function arising from a concave function."Discrete Applied Mathematics. 92. 211-215 (1999)

S. Fujishige 和 S. Iwata：“最小化由凹函数引起的子模函数。”离散应用数学。

S.Fujishige: Linear Algebra and Its Applications. 279. 75-91 (1998)

S.Fujishige：线性代数及其应用。

S. Fujishige: "Another simple proof of the validity of Nagamochi and Ibaraki's min-cut algorithm and Queyranne's extension to symmetric submodular function minimization."Journal fo the Operations Research Society of Japan. 41. 626-628 (1998)

S. Fujishige：“Nagamochi 和 Ibaraki 的最小割算法以及 Queyranne 对对称子模函数最小化的扩展的有效性的另一个简单证明。”日本运筹学会杂志。

S.Fujishige,X.Liu and X.Zhang: "An algorithm for solving the minimum norm point over the intersection of a polytope and an affine set"Journal of Optimization Theory and Applications. (to appear).

S.Fujishige，X.Liu和X.Zhang：“求解多面体和仿射集交集上的最小范数点的算法”优化理论与应用杂志。

S. Fujishige and S. Iwata: "Algorithms for submodular flows"IEICE Transactions. (to appear).

S. Fujishige 和 S. Iwata：“子模流算法”IEICE Transactions。