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

点击翻译按钮获取中文摘要

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.