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

作     者：任建峰 田晓云 REN Jianfeng;TIAN Xiaoyun

作者机构：曲阜师范大学管理学院、运筹学研究院山东日照276826 

出 版 物：《运筹学学报》 (Operations Research Transactions)

年 卷 期：2021年第25卷第1期

页      面：114-122页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：山东省自然科学基金(Nos.ZR2014AM012,ZR2017MA031,ZR2019MA061) 山东省高等学校科技计划(No.XKJ201315) 国家自然科学基金(No.11771251) 

主　　题：异常点 设施选址 近似算法 原始对偶算法 NP-难 

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