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

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

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.