多面体组合是组合最优化领域前沿的研究方向,其中装填与覆盖问题是多面体组合中经典的问题.由于许多组合优化问题都可以用超图的语言描述为装填与覆盖类型的问题,近几十年来装填与覆盖问题受到了专家学者的广泛关注和深刻研究.研究装填与覆盖问题需要综合运用多面体组合学、图论、计算复杂性等学科的理论和技巧.刻画对偶整数性及盒式对偶整数性、建立最小最大定理、设计有效的多项式时间算法及近似算法是研究装填与覆盖问题的核心内容.本项目研究两类重要的装填与覆盖问题:圈装填与圈覆盖问题,反馈弧集装填与反馈弧集覆盖问题.本项目的主要目的是刻画在给定的装填与覆盖问题中相应的线性系统满足对偶整性及盒式对偶整性的图类,导出深刻而优美的Min-Max定理,并设计简洁高效的多项式时间组合算法及近似算法.

Polyhedral combinatorics is a frontier research direction in the field of combinatorial optimization. As a rich variety of combinatorial optimization problems can be described as packing-covering type problems in the language of hypergraphs, packing and covering problems have attracted tremendous attention of many researchers and have been studied extensively over the last several decades. To study packing and covering problems, one needs to comprehensively utilize the theories and techniques from multiple disciplines, such as polyhedral combinatorics, graph theory, computational complexity and so on. The core of the research on packing and covering problems is to characterize the dual integrality and the box-dual integrality, establishing Min-Max theorems, and to design efficient polynomial-time algorithms and approximation algorithms. In this project, we propose to investigate two important classes of packing and covering problems: cycle packing and covering problem, feedback arc set packing and covering problem. The main purpose of this project is to identify those graph classes for which the corresponding linear systems satisfy the dual integrality or the box-dual integrality in the given packing and covering problem, derive profound and elegant Min-Max theorems, and devise succinct and efficient polynomial-time combinatorial algorithms and approximation algorithms.