最小权p联合问题及其相关问题的近似算法

This project aims to study computational complexities and approximation algorithms for the minimum weight p union (MinpU) problem and its related problems. MinpU aims to choose at least p hyperedges in a given hypergraph such that the sum of the vertex weight in the union of the chosen hyperedges is smallest. Because of its rich applications in the real world and its close relationship with some hot combinatorial optimization problems such as the maximum k densest sub-graph problem, MinpU problem has attracted a lot of attention recently. Researches on this topic are just beginning and there are a lot of problems to be explored.. This project will use mathematical tools including computational complexity theory, combinatorial optimization and submodular optimization to study the lower bounds for the approximability of MinpU problem, design approximation algorithms for the MinpU problem, explore the MinpU problem in some typical structures and design polynomial algorithm to obtain tight approximation ratios. This project aims to push the progress of studies on MinpU and its related problems by exploring new ideas and developing new methods.

本项目拟研究最小权p联合(MinpU)问题以及其相关问题的计算复杂性和近似算法。MinpU问题的目标是在超图中选择至少p条超边使得这些超边之并的点权之和最小。MinpU问题因与最大密度k子图(DkS)等热点优化问题紧密相关，以及其在现实世界中丰富的应用背景，受到研究者们的广泛关注。该课题近似算法方面的研究才刚刚起步，具有很大的研究空间。. 本项目将综合应用计算复杂性理论、组合优化和次模优化等多种数学工具，研究MinpU问题计算复杂性下界，探索赋权MinpU问题的近似算法，并研究典型结构上的MinpU问题，设计多项式时间算法，力求得到紧的近似比。期望通过本项目的研究，探索新的思想和方法，为MinpU及其相关问题的研究做出贡献。

本项目聚焦了最小权p联合(MinpU)问题以及其相关问题的近似算法并给出理论分析。以本项目为依托，共培养硕士研究生两名，发表论文8篇。其中包含：.（1）针对最小部分多重覆盖问题在单位正方形背景下的近似算法，在一定的覆盖需求下得到了常数近似。.（2）针对最小能量部分多重覆盖问题，在最大覆盖需求是常数的条件下得到了PTAS的结果。.（3）针对最小部分覆盖问题的并行算法，在运行轮数为输入规模的对数多项式量级下得到渐近于串行算法下的最好结果。.（4）针对单位圆盘图上的最小部分控制集问题的并行算法，在运行轮数为输入规模的对数多项式量级下得到常数近似。.（5）针对最小次模覆盖问题的并行算法，在运行轮数为输入规模的对数多项式量级下得到渐近于串行算法下的最好结果。.（6）针对最小罗马（连通）控制集问题，通过贪婪算法得到渐近于近似比下界的结果。.（7）针对最小能量部分覆盖问题，通过原始对偶算法得到了常数近似。