装填与覆盖问题的对偶整数性及算法研究

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.

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

多面体组合学是组合最优化领域前沿的研究方向之一。装填与覆盖问题是多面体组合学中的经典研究课题，可以用来描述许多重要的组合优化问题。刻画给定线性系统的全对偶整数性及盒式全对偶整数性、建立最小最大定理、设计有效的多项式时间算法及近似算法是本项目的实施要点。本项目在圈装填与圈覆盖问题、图密度及分式边着色问题、图的co-density问题、分式边覆盖装填问题及若干双指标排序问题上进行了深入的研究，并取得了较为系统的研究成果。受本项目资助已发表学术论文7篇。代表性成果如下：（1）完整刻画了任意多个顶点的cycle Mengerian 竞赛图，证明了竞赛图T是cycle Mengerian 当且仅当T不包含4个禁用子图作为导出子图。这一结果是首次给出cycle Mengerian 非平面有向图类的刻画；（2）设计了分式边着色问题和图密度问题的强多项式时间组合算法，从而解决了由Jensen和Toft(2015)及Stiebitz(2012) 等人在其著作中列出的公开问题；（3）研究了图的co-density 问题及分式边覆盖装填问题，这两个问题是文献中的遗留问题，我们设计了有效的强多项式时间组合算法；（4）对于单机上的双指标Pareto优化问题，目标函数是同时最小化误工工件个数和最大化机器开工时间， 我们设计了新的时间界为O(nlogn)的算法，改进了文献中已有的结果；（5）引入了单机GCT排序模型，并以此为工具系统地研究了一致机上等长工件约束下的若干双指标排序问题，将文献中的关于等长工件双指标排序问题的大多数结果进行了推广或改进，其中一个结果解决了Sarin 和Prakash (2004)提出的公开问题。