k-中位问题的近似算法  

Survey on approximation algorithms for the k-median problem

作　　者：吴晨晨[1] 杜东雷 苗润杰 徐大川[4] Chenchen Wu;Donglei Du;Runjie Miao;Dachuan Xu

机构地区：[1]天津理工大学理学院运筹学与系统工程研究所,天津300384 [2]Faculty of Management,University of New Brunswick,Fredericton E3B 5A3,Canada [3]郑州大学数学与统计学院,郑州450001 [4]北京工业大学数学统计学与力学学院,北京100124

出　　处：《中国科学:数学》2025年第2期551-566,共16页Scientia Sinica:Mathematica

基　　金：国家自然科学基金(批准号:12371320)资助项目。

摘　　要：k-中位问题是理论计算机科学和组合优化领域中的经典问题之一,其应用场景遍及图像处理、模式识别、供应链管理和数据挖掘等前沿领域.如今,随着大数据和机器学习的发展,k-中位问题的实际应用愈发复杂多样,这也产生了诸多亟待解决的研究课题.为使相关研究人员快速了解k-中位问题,本文综述经典k-中位问题及其变型问题的基于线性规划舍入、原始-对偶、对偶拟合、局部搜索和Lagrange松弛等技巧设计的有效算法.首先介绍经典k-中位问题与无容量设施选址问题之间的密切联系;然后介绍k-中位问题的若干重要变形,包括k-中心问题、k-设施选址问题、背包中位问题、容错k-中位问题、带容量的k-中位问题、带下界的k-中位问题、带惩罚的k-中位问题、带异常值的k-中位问题和在线中位问题等问题;最后介绍k-中位问题的近似算法研究成果,并列出该领域中的若干公开问题.The k-median problem is one of the classical topics in the fields of theoretical computer science and combinatorial optimization,which is widely applied to image processing,pattern recognition,supply chain management,and data mining.Nowadays,with the development of big data and machine learning techniques,the practical applications of the k-median problem become more and more complex.This leads to a variety of new research topics that need to be solved urgently.In this paper,we introduce effective algorithms based on linear programming rounding,primal-dual,dual-fitting,local search,Lagrange relaxation,and other techniques for the classical k-median problem and its variants.We begin with the close relation between the k-median problem and the uncapacitated facility location problem.Then we introduce several important variants of the k-median problem including the k-center problem,k-facility location problem,knapsack median problem,fault-tolerant k-median problem,capacitated k-median problem,k-median problem with lower bounds,k-median problem with penalties,k-median problem with outliers,and online median problem.Finally,we survey the approximation algorithms for the k-median problem and propose several open problems in this area.

关 键 词：k-中位问题 近似算法 线性规划 局部搜索 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]