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

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

本项目基于超图结构的对偶整数性理论，研究与之相关的装填与覆盖问题，分析了特殊图论结构，发展了算法，得到了以下结果：1. 刻画优化问题的离散结构在设计算法方面起着关键的作用；2. 提供了判断给定超图是Box－Mengerian超图的行之有效的充分条件；3. 对经典Facility location问题进行了研究，刻画了一类满足特定条件的有界整数多面体,并对基于该类特殊结构之上的Facility location问题设计了多项式时间算法，并得到了基于其上的两个最大最小关系。上述结果表明我们的方法是研究各种装填和覆盖问题的一个强有力工具，为后续的研究提供一个基础和方向。