基于超图结构的对偶整数性理论及其相关的装填与覆盖问题研究

超图上的装填与覆盖问题，因其能描述绝大多数的组合最优化问题，一直是研究优化问题、算法设计和Min-Max定理的中心之一。但在一般情形下，超图上的装填问题和覆盖问题都是NP-难的，因此除非P=NP，否则超图上的装填或覆盖问题均不能在多项式时间之内解决。本项目的主要目的是探求在何种条件下超图上的装填或覆盖问题可被多项式时间算法求解。本项目拟从线性规划对偶理论角度，研究特定条件下满足TDI系统或Box-TDI系统的超图；提出ESP超图概念；提出基于对偶整数性理论的有效算法；给出若干Min-Max定理。本项目是国际上一个传统而前沿的研究方向，需要综合应用组合最优化、图论和多面体组合学等学科的理论与技巧。预期获得的结论可为部分离散结构的刻画提供理论依据，有助于对基于这些离散结构上的相关优化问题的求解设计有效算法或近似算法，并有助于对组合最优化领域中的若干重要定理和猜想给予重新解释和统一处理。