Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures

我们研究了大规模离散优化问题，特别注意子模块结构，这是有效的设计高效的算法。具体来说，我们已经研究了离散优化问题相关的网络流，匹配，多流，设施位置，资源分配，图连通性，通信网络设计，和嵌入网络，离散结构出现在双贪婪算法，如双贪婪多面体和zonotopes，离散结构的霍恩函数和稳定匹配问题，通过对单个离散结构的知识和见解的整合，建立基本理论和快速算法。

We have investigated large-scale discrete optimization problems by paying special attention to submodular structures which are effective to devise efficient algorithms. Specifically we have examined discrete optimization problems related to network flows, matchings, multiflows, facility location, resource allocation,graph connectivity, communication network design, and queueing networks, discrete structures arisen in dual greedy algorithms such as dual greedy polyhedra and zonotopes,discrete structures for Horn functions and stable matching problems, and so on to establish the fundamental theory and fast algorithms by integrating the knowledge and insights gained on the individual discrete structures．