部分集合多重覆盖问题的近似算法

This project aims to study approximation algorithms for the minimum partial set multi-cover problem (PSMC). Set Cover is a classic combinatorial optimization problem, which is highly esteemed in the fields of computational complexity and approximation algorithm. Because of its wide applications in the real world, it is also a hot problem in information sciences, social sciences, management sciences, and biological sciences. Both multi-cover problem and partial cover problem have tight approximation ratios which match those best ratios for the classic set cover problem. However, previous studies show that combining these two factors together enormously increases the difficulty of study. Any breakthrough on PSMC will be of great theoretical value and application value..Faced with new challenges proposed by PSMC, this project will use various mathematical tools including combinatorial optimization, convex program, probabilistic theory, computational complexity theory, graph theory, geometry etc. to design new approximation algorithms and provide strict theoretical guarantees; explore new local algorithms which are fast and effective; analyze its computational complexity and try to determine the inapproximability class that PSMC belongs to; and for a special case of PSMC, namely, the minimum partial positive influence dominating set problem which stems from social network, try to make full use of graph structure to achieve better algorithm and better performance. The PSMC problem belongs to the field of nonlinear combinatorial optimization (NCO). This project aims to contribute to the development of NCO by exploring new methods for PSMC.

本项目研究部分集合多重覆盖问题(PSMC)的近似算法。覆盖问题是组合优化中的一个经典问题，在计算复杂性理论和近似算法领域都占有重要地位，因其在现实世界中的广泛应用，也是信息科学、社会科学、管理科学、生命科学等领域的热点问题。多重覆盖问题和部分覆盖问题都已有紧的近似比，但前期研究表明把这两个因素结合起来使得研究难度骤增，该问题的研究一旦取得突破将具有巨大的理论价值和应用价值。.本项目拟综合应用组合优化、凸规划、概率论、图论、几何学等多种数学工具，针对PSMC提出的新挑战，设计新的近似算法并提供严格理论分析，探索快速有效的局域算法，研究其计算复杂性，力求确定该问题所在的不可近似类，并进一步研究PSMC问题的一个特例——部分正影响控制集问题，利用图的结构性质得到比一般理论更好的近似比。PSMC问题属于非线性组合优化领域，本项目拟通过对它的研究探索新的研究方法，为非线性组合优化的发展贡献一份力量。

以社交网络及无线传感网络中的应用需求为背景，聚焦部分集合多重覆盖问题(PSMC)及其相关问题，设计高效近似算法，提供严格理论保证。发表学术论文53篇，其中SCI论文38篇，出版专著1部，培养博士生3名，硕士生8名。具体研究成果包括：.1、在PSMC问题上：证明了计算复杂性不低于最稠密k子图问题，从而很难有亚多项式近似比；设计了一系列随机算法和确定性算法，得到了目前最好的近似比；在特殊结构上设计了具有更优性能的算法，包括：最小能量部分覆盖问题和单位圆盘图上最小部分控制集问题的并行算法，在对数多项式时间内，近似比接近串行算法的最优近似比。.2、在容错连通控制集近似算法方面取得突破，包括(3,m)-CDS目前最好的近似比；对一般的常数k和m≥k，一般图上(k,m)-CDS的第一个有近似比保证的算法。.3、对点删除问题，设计了最小权连通3路覆盖的渐近最优近似算法；提出划分扩张的思想，极大简化了单位圆盘图上连通k路覆盖问题的PTAS近似算法及其时间复杂度；率先研究了在线3路覆盖问题，得到了紧的竞争比。 .4、提出了两种新的扫描覆盖问题，具有距离限制的扫描覆盖问题和prize-collecting扫描覆盖问题，给出了一系列有近似比保证的算法。.5、纠正了前人在障碍覆盖最大生命期问题中的错误，设计了一个固定参数算法；提出了衡量屏障覆盖质量的新参数：屏障覆盖的宽度，研究了其计算复杂度和算法；对于传感器在线级联修复问题，设计了首个有竞争比保证的算法：提出度平衡支撑树问题，结合差分方程，设计了一个非线性原设对偶算法；开辟了部分最大支撑树逆问题近似算法的研究。.6、设计了覆盖问题的博弈算法，系统地研究了移动众包问题的激励机制，在计算复杂性、诚信性、可持续性、和激励效果方面都有较好的表现。.7、出版学术专著《Optimal Coverage in Wireless Sensor Networks》，系统地介绍了覆盖问题理论研究的经典结果、典型方法、和最新动态，其中包括大量本团队的研究成果。