带容量k-平均问题的近似算法研究

The k-means problem attracts focus from both industry and academia since it was proposed last centenary, and eventually grows to be an interdisciplinary significant and hard problem. This project considers the approximation algorithm research on the k-means problem under a significant environment, the capacitated k-means problem. The capacity constraint is always the most nature and straightforward constraint, but for the capacitated k-means, the algorithm results are very limited. The main reasons is that it is hard to cope with both the cardinality and capacity constraints at the same time, which makes it harder than the k-means problem. Another reason is that most researchers from other areas have no experiences to deal with multi-constraints from the approximation ratio and running time perspective. Therefore, we propose this project of the approximation algorithm research for the capacitated k-means problem in order to complete the theoretical algorithm framework and satisfy the requirement of application demand, which is of great theoretical and practical significance.

k-平均问题自上世纪提出以来就受到了业界和学术界的广泛关注，并逐渐发展成为多学科交叉领域的重点和难点问题。本项目关注k-平均问题在一类重要场景下的近似算法研究：带容量k-平均问题。容量约束几乎是所有组合优化问题最自然和直观的约束，但带容量约束的k-平均问题的算法研究非常有限。主要原因是带容量约束的k-平均问题要求同时满足基数和容量约束，处理起来十分困难；其次来自其他领域的学者大部分不具备处理双重硬性约束的算法优化经验，很难从算法精度和时间上优化k-平均算法。因此，本项目提出带容量k-平均问题的近似算法研究，是为了完善k-平均问题的理论算法框架和适应业界的实际应用需求，具有非常重要的理论和实际意义。

k-平均问题自上世纪提出以来就受到了业界和学术界的广泛关注，并逐渐发展成为多学科交叉领域的重点和难点问题。本项目关注k-平均问题在一类重要场景下的近似算法研究：带容量k-平均问题。容量约束几乎是所有组合优化问题最自然和直观的约束，但带容量约束的k-平均问题的算法研究非常有限。主要原因是带容量约束的k-平均问题要求同时满足基数和容量约束，处理起来十分困难。本项目迎难而上，得到了该问题的一系列正面结果，首次提出了带容量k-平均问题FPT(k)时间内的常数近似算法，开辟了研究带容量k-平均问题参数化算法的路径。基于此，我们还延续了容量约束的聚类问题的相关研究，累计在项目支持下发表论文8篇(其中一作/通讯5篇)，举办算法领域国际会议5次(其中COCOON于2022年增选为理论计算机CCF-B类国际会议)，在领域内产生了一定影响力。