典型文献
带惩罚的相同容量k-均值问题的局部搜索算法
文献摘要：
经典k-均值问题是一类应用广泛的聚类问题,它是指给定(R)d中观测点集合D和整数k,目的是在空间中寻找k个点作为中心集合S,使得集合D中的每个观测点到S中离它最近的中心的距离平方求和最小.这是个NP-难问题.经典k-均值问题有很多推广,本文研究的带惩罚的相同容量k-均值问题就是其中之一.与经典k-均值问题相比,惩罚性质是指每个观测点都给定惩罚费用,当某个观测点到最近中心的距离大于惩罚费用时,其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方,相同容量约束要求每个中心至多连接U个观测点.针对这种问题,我们设计了局部搜索算法,该算法在至多选取(3+α)k个中心的情况下,可以达到β-近似,其中,参数α＞34,β＞α+34/α-34.
文献关键词：
k-均值问题;惩罚;相同容量;双准则;局部搜索;近似算法
中图分类号：
作者姓名：
剧嘉琛;刘茜;张昭;周洋
作者机构：
北京工业大学数学学院运筹学与信息工程系,北京100124;山东师范大学数学与统计学院,山东济南250014;浙江师范大学数学与计算机科学学院,浙江金华321004
文献出处：
引用格式：
[1]剧嘉琛;刘茜;张昭;周洋-.带惩罚的相同容量k-均值问题的局部搜索算法)[J].运筹学学报,2022(01):113-124
A类：
B类：
相同容量,局部搜索算法,聚类问题,指给,观测点,点集,整数,NP,惩罚性,某个,容量约束,至多,3+,+34,双准则,近似算法
AB值：
0.311698
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
