带有异常点的平方度量设施选址问题

• 作者: 任建峰 田晓云
• 来源期刊: 运筹学学报
• 关键词: 异常点 设施选址 近似算法 原始对偶算法 NP-难
• 年，卷（期）: 2021,（1）
• 页码范围: 114-122
• 页数: 9页
• 分类号: O221.7
• 语种: 中文
• DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.011

摘要

传统的设施选址问题一般假设所有顾客都被服务,考虑到异常点的存在不仅会增加总费用(设施的开设费用与连接费用之和),也会影响到对其他顾客的服务质量.研究异常点在最终方案中允许不被服务的情况,称之为带有异常点的平方度量设施选址问题.该问题是无容量设施选址问题的推广.问题可描述如下:给定设施集合、顾客集,以及设施开设费用和顾客连接费用,目标是选择设施的子集开设以满足顾客的需求,使得设施开设费用与连接费用之和最小.利用原始对偶技巧设计了近似算法,证明了该算法的近似比是9.