超图上装填与覆盖问题的对偶整数性质及其算法设计研究

Serving as a unified and beautiful framework in theory, packing or covering problems in hypergraphs can formulate many combinatorial optimization problems of both practical and theoretical importance, and within the general framework, deep mathematical results have been derived over the past few decades, showing a far-reaching practical impact of this framework. The subject of studying packing or covering Problems in hypergraphs has become one of the important research centers in modern discrete mathematics, with strong links to Min-Max theorems, polyhedral combinatorics, graph theory and theory of algorithms. In general, packing and covering problems in hypergraphs are NP-hard, therefore neither of them can be solved exactly in polynomial time unless P=NP. The main objective of this project is to study the dual integrality conditions and the design principles of efficient algorithms for various packing and covering problems in hypergraphs. From the perspectives of both computational complexity and polyhedral combinatorics, this project aims at exploring TDI and Box-TDI properties.associated with hypergraphs, characterizing underlying combinatorial structure of various problems, designing efficiently exact or approximation algorithms based on dual integralities of the problem, and establishing some Min-Max theorems. Since the project proposes to deal with issues that have been the subject of extensive research in history and have attracted tremendous efforts in recent years, it aims to combine theories with techniques from multiple disciplines such as computational complexity, polyhedral combinatorics, graph theory, theory of algorithms and so on. This project is expected to yield findings that may be both valuable and significant for the characterizations of some important discrete structures, as well as the designs of some efficiently exact or approximation algorithms for the associated combinatorial optimization problems upon these discrete structures.

超图上的装填与覆盖问题能统一而优美地描述绝大多数组合最优化问题，能导出深刻的数学理论并产生深远的实际影响，是现代离散数学中综合研究Min-Max定理、多面体组合学、图论和算法理论等重要内容的中心之一。但一般情形下，超图上的装填问题和覆盖问题都是NP-难的，因此除非P=NP，否则超图上的装填或覆盖问题均不能在多项式时间之内解决。本项目的主要目的是研究超图上装填与覆盖问题的对偶整数性质及其相关问题的有效算法设计。本项目拟从计算复杂性和多面体组合学角度，研究特定条件下满足TDI或Box-TDI系统的超图; 提出基于对偶整数性质的有效算法；导出若干Min-Max定理。本项目属于国际上核心而前沿的研究方向，需要综合应用复杂性理论、多面体组合学、图论和算法理论等学科的理论与技巧。预期获得的结论可为部分离散结构的刻画提供理论依据，有助于对相关重要优化问题的求解设计有效算法。

本项目基于超图结构的对偶整数性理论，研究与之相关的装填与覆盖问题和一些关系紧密的组合最优化问题，发展了算法，刻画了所涉及问题的结构，得到了以下结果：1. 刻画了孟格图（Mengerian graphs）的结构并设计了多项式时间算法求解孟格图上的装填与覆盖问题，作为副产品，给出了求解二部图上带权重的顶点覆盖问题的新算法；2. 研究了NP-难边覆盖装填问题（edge cover packing problem（ECPP））的松弛问题：分数边覆盖装填问题（fractional edge cover packing problem (FECPP)），对该问题给出了基于组合结构的多项式时间算法；3. 研究了经典平行机排序问题加工时间为满足整除关系下的多项式时间算法可解性，刻画了一个组合性质，并利用其设计了多项式时间算法求解此特殊情形，并根据该组合性质为一般情形设计了一个3/2近似算法。为相关的一些带有装填或覆盖性质问题的NP-难问题设计基于多项式可解性特殊结构的近似算法，提供了新思路。装填与覆盖往往以隐秘的方式出现在组合最优化问题中，本项目组的结果表明，用装填与覆盖的眼光看待组合最优化问题，并刻画相应的结构，得到特殊情形下的多项式时间算法是针对NP-难问题求解的重要基础，对设计好的近似算法至关重要。