k-中位问题的理论与算法研究

The k-median problem, as one of the classical combinatorial optimization problems, has a lot of applications on location problems such as location of logistics distribution center, mobile communication base station, computer network design, and power grid design. It is also widely used in data mining technology as a clustering algorithm. According to the needs of different practical problems, various variants can be derived from k-median, such as capacitated k-median, fault-tolerant k-median, k-median with penalties, knapsack median, and matroid median problems. These variants, as well as k-median problem are NP-hard. From the perspective of approximation algorithm, in this project we will study the k-median problem and its variants using the LP-rounding, local search, primal-dual techniques, etc. In particular, for some problems which only have LP-rounding algorithm so far, more efficient combinatorial algorithms will be designed in this project, such as local search and primal-dual algorithms.

k-中位问题是经典的组合优化问题之一，在各种选址问题如物流配送中心的选址、移动通信基站的选址、计算机网络设计、以及电网设计中有大量的应用，同时作为一种聚类算法被广泛应用于数据挖掘技术中。根据实际问题的需要，k-中位问题可以衍生出很多种变形，例如带容量约束的k-中位问题，容错的k-中位问题，带惩罚的k-中位问题，背包中位问题，拟阵中位问题等等。k-中位问题和这些变形都是NP-难的。本项目将从近似算法的角度，使用线性规划舍入、局部搜索和原始对偶等技术对k-中位问题及其变形进行研究。特别是，针对一些目前只存在线性规划舍入算法的问题，本项目将使用局部搜索和原始对偶技术为其设计更加高效的组合算法。

本项目围绕组合优化中经典的具有深刻现实意义的NP-难问题，从近似算法角度进行研究。研究的问题主要包括下界k-中位问题、下界背包中位问题、球面k-均值问题、带惩罚的k-均值问题、带惩罚/异常点的球面k-均值问题，带异常点的k-层设施选址问题、带容量（硬容量/软容量）约束的k-均值问题、关联聚类问题、下界相关聚类问题等均取得了预期研究成果。并且在研究上述问题过程中很好地将不同问题的算法设计技巧相融合，对后续研究提供了更多的思路和启发。在本项目支持下共发表期刊论文35篇，会议论文18篇。.随着科学技术的发展，信息的及时性、准确性和大数据性扮演的角色日益重要，在以前的研究中认为切合实际的模型变得日益远离实际。本项目对当今科技水平下的诸多现实问题抽象出了更加贴切也更加广义的模型，在前人研究技巧上加以创新和推广，提出了我们的新型近似算法。.本项目研究了下界背包中位问题和下界k-中位问题，分别得到了1608-近似和(α, (1+α)ρ/(1-α))-双准则近似。结合现实有关鲁棒k-中位问题的多种变形，我们研究了带惩罚的k-均值问题、带惩罚/异常点的球面k-均值问题、异常点的k-层设施选址问题、带容量（硬容量/软容量）约束的k-均值问题等。球面-均值聚类是最具有代表性的文本聚类方法之一，通过挖掘球面k-均值问题的结构，我们利用局部搜索技术给出了球面k-均值问题(13.2916+ε)-近似算法。通过研究局部搜索算法及对其性能分析，可以帮助了解球面k-均值问题局部最优算法的性质。此外，我们将k-均值++初始化算法和k-均值并行初始化应用于带惩罚的k-均值问题，对任意的迭代次数及每次迭代任意的采样点数均给出充分的解的质量分析，克服了原有算法的缺陷，推广了解决k-均值问题的方法。本项目还研究了关联聚类问题、下界相关聚类问题。作为技巧的延伸，本项目还研究了最大化次模函数问题、非原子拥堵博弈问题的PoA等。