Fundamental Research on Fast Algorithms for Large-Scale Discrete Optimization Problems Based on Submodularity Structures

基于子模结构的大规模离散优化问题快速算法基础研究

• 批准号: 13480113
• 负责人: FUJISHIGE Satoru
• 金额: $ 4.61万
• 依托单位: KYOTO UNIVERSITY (2003)Osaka University (2001-2002)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-13480113/
• 关键词: Algorithms; Discrete Optimization; Combinatorial Optimization; Submodular Functions; Large-Seal Systems

Major research results we obtained are the following :1. We proposed efficient algorithms for source location, problems with flow requirement, which was based on the submodularity of cut functions of the underlying flow network.2. We presented new algorithms for maximum matchings in regular bipartite graphs and for maximum flows in directed networks by means of maximum-adjacency ordering.3. We showed a new approach to submodular function minimization problem presenting an O(n^2) algorithm using the membership oracle for base polyhedra.4. We revealed the equivalence between discrete convexity and the gross substitutes condition in economics, and using discrete concave utility functions, we extended the concept of stable marriage due to Gale and Shapley and showed the existence of stable solutions algorithmically.5. We introduced the concept of polybasic polyhedron by generalizing that of base polyhedron, a fundamental submodularity structure, which lead us to a new general framework for polyhedral structure of submodularity.6. We presented a sequential pseudo-polynomial algorithm for enumerating minimal integral solutions of monotone linear systems.7. We showed the hardness of enumerating maximal frequent sets and the polynomial-time solvability of enumerating minimal non-frequent sets.

主要研究成果如下：1.基于底层流网络割函数的子模性，提出了流需求源定位问题的有效算法.利用最大邻接序给出了正则二部图最大匹配和有向网络最大流的新算法.我们提出了一种新的方法来解决子模函数极小化问题，给出了一个O（n^2）的算法，使用了基多面体的成员预言。揭示了离散凸性与经济学中总替代条件的等价性，并利用离散凹效用函数，推广了Gale和Shapley的稳定婚姻概念，给出了稳定解的存在性算法.通过推广基多面体的概念，引入了多面体的概念，从而得到了一个新的子模多面体结构的一般框架.提出了一种序列伪多项式算法，用于求解单调线性方程组的极小积分解.证明了最大频繁集计数的困难性和最小非频繁集计数的多项式时间可解性。

项目成果

H.Ito, K.Makino, K.Arata, S.Honami, Y.Itatsu, S.Fujishige: "Source location problem with flow requirements in directed networks"Optimization Methods and Software. 18. 427-435 (2003)

H.Ito、K.Makino、K.Arata、S.Honami、Y.Itatsu、S.Fujishige：“有向网络中流量需求的源定位问题”优化方法和软件。

T.Ibaraki, A.Kogan, K.Makino: "Inferring minimal functional dependencies in Horn and q-Horn theories"Annals of Mathematics and Artificial Intelligence. 38. 233-255 (2003)

T.Ibaraki、A.Kogan、K.Makino：“推断 Horn 和 q-Horn 理论中的最小函数依赖性”数学与人工智能年鉴。

H.Ono, K.Makino, T.Ibaraki: "Logical analysis of data with decomposable structures"Theoretical Computer Science. 289. 977-995 (2002)

H.Ono、K.Makino、T.Ibaraki：“具有可分解结构的数据的逻辑分析”理论计算机科学。

E.Boros, T.Horiyama, T.Ibaraki, K.Makino, M.Yagiura: "Finding essential attributes in binary data"Annals of Mathematics and Artificial Intelligence. 39. 223-257 (2003)

E.Boros、T.Horiyama、T.Ibaraki、K.Makino、M.Yagiura：“在二进制数据中寻找基本属性”数学与人工智能年鉴。

E.Boros: "Dual-bounded generating problems : All minimal integer solutions for a monotone system of linear inequalities"SIAM Journal on Computing. 31. 1624-1643 (2002)

E.Boros：“对偶有界生成问题：线性不等式单调系统的所有最小整数解”SIAM 计算杂志。