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

doi:10.15960/j.cnki.issn.1007-6093.2021.01.011

运筹学学报 ›› 2021, Vol. 25 ›› Issue (1): 114-122.doi: 10.15960/j.cnki.issn.1007-6093.2021.01.011

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

任建峰¹, 田晓云¹^,*()

1. 曲阜师范大学管理学院、运筹学研究院, 山东日照 276826

收稿日期:2018-11-19 出版日期:2021-03-15 发布日期:2021-03-05
通讯作者: 田晓云 E-mail:xiaoyun_txy@163.com
作者简介:田晓云 E-mail: xiaoyun_txy@163.com
基金资助:
山东省自然科学基金(ZR2014AM012);山东省自然科学基金(ZR2017MA031);山东省自然科学基金(ZR2019MA061);山东省高等学校科技计划(XKJ201315);国家自然科学基金(11771251)

Squared metric facility location problem with outliers

Jianfeng REN¹, Xiaoyun TIAN¹^,*()

1. Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, Shandong, China

Received:2018-11-19 Online:2021-03-15 Published:2021-03-05
Contact: Xiaoyun TIAN E-mail:xiaoyun_txy@163.com

摘要/Abstract

摘要：

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

关键词: 异常点, 设施选址, 近似算法, 原始对偶算法, NP-难

Abstract:

Traditionally, we assume that all the clients to be provided service in the facility location problems. In our study, we explore the case when only a fraction of clients allow to be denied service in the final solution. Indeed, the existence of outliers will not only increase the total cost, but also have an undesirable effect on the service quality of other clients. We consider the squared metric facility location problem with outliers, which is a generalization of the classic uncapacitated facility location problem. Next we will give a detailed description of the problem. Given a set of facilities with open cost and a set of clients with connection costs, we seek a subset of facilities to open and satisfy the demands of clients. The objective is to minimize the sum of total open and connection cost. We utilize the primal-dual scheme to design an approximation algorithm, and prove that the proposed algorithm is a 9-approximation.

Key words: outliers, facility location, approximation algorithm, primal-dual scheme, NP-Hard

中图分类号:

O221.7

任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.

Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers[J]. Operations Research Transactions, 2021, 25(1): 114-122.

图/表 3

参考文献 22

1	Vazirani V . Approximation Algorithms[M]. Berlin: Springer-Verlag, 2001.
2	Williamson D , Shmoys D . The Design of Approximation Algorithms[M]. Cambridge: Cambridge University Press, 2011.
3	Hochbaum D . Heuristics for the fixed cost median problem[J]. Mathematical Programming, 1982, 22, 148- 162. doi: 10.1007/BF01581035
4	Shmoys D, Tardös É, Aardal K. Approximation algorithm forfacility location problems[C]//Proceedings of the 29thAnnual ACM Symposium on Theory of Computing, 1997, 265-274.
5	Jain K , Vazirani V . Primai-dual approximation algorithms for metricfacility location and k-median problems using the primal-dualschema and lagarangian relaxation[J]. Journal of the ACM, 2001, 48, 274- 296. doi: 10.1145/375827.375845
6	Korupolu M , Plaxton C , Rajaraman R . Analysis of a local searchheuristic for facility location problems[J]. Journal ofAlgorithms, 2000, 37, 146- 188. doi: 10.1006/jagm.2000.1100
7	Li S. A . 1.488 approximation algorithm for the uncapacitated facilitylocation problem[J]. Information and Computation, 2013, 222, 45- 58. doi: 10.1016/j.ic.2012.01.007
8	徐大川, 许宜诚, 张冬梅. k-平均问题及其变形的算法综述[J]. 运筹学学报, 2017, 21, 101- 109.
9	徐大川, 许宜诚, 张冬梅. k-均值算法的初始化方法综述[J]. 运筹学学报, 2018, 22, 31- 40.
10	Charika M, Guha É, Shmoys D. A constant-factor approximation algorithm for the k-median problem[C]//Proceedings ofthe 31st Annual ACM Symposium on Theory of Computing, 1999: 1-10.
11	Ye Y, Zhang J. An approximation algorithm for the dynamic facilitylocation problem[M]//Combinatorial Optimization inCommunication Networks, New York: Kluwer Academic Publishers, 2005, 623-637.
12	Fernandes C , Meira L , Miyazawa F , et al. A systematic approachto bound factor-revealing LPs and its application to the metric andsquared metric facility location problems[J]. Mathematical Programming, 2015, 153, 655- 685. doi: 10.1007/s10107-014-0821-x
13	姜燕君, 徐大川, 张冬梅. 平方度量动态设施设施选址问题的近似算法[J]. 运筹学学报, 2018, 22, 49- 58.
14	Chudak F , Shmoys D . Improved approximation algorithms for theuncapacitated facility location problem[J]. SIAM Journal onComputing, 2003, 33, 1- 25. doi: 10.1137/S0097539703405754
15	Charikar M, Khuller S, Mount M, Narasimhan G. Algorithms for facility location problems with outliers[C]//Proceedings of the 12st Annual ACM-SIAM Symposium on Discrete Algorithms, 2001: 642-651.
16	Jiang Y , Xu D , Du D , et al. An approximation algorithm for the dynamic facility location problem with outliers[J]. Optimization Letters, 2019, 13, 561- 571. doi: 10.1007/s11590-017-1153-6
17	Byrka J , Aardal K . An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem[J]. SIAM Journal on Computing, 2010, 39, 2212- 2231. doi: 10.1137/070708901
18	Vygen J. Approximation algorithms for facility location problems[R]. Technical Report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, 2005.
19	Chen K. A constant factor approximation algorithm for k-median clustering with outliers[C]//Proceedings of the 19st Annual ACM-SIAM Symposium on Discrete Algorithms, 2008: 826-835.
20	Mangasarian O . Mathematical programming in data mining[J]. Data Mining and Knowledge Discovery, 1997, 1, 183- 201. doi: 10.1023/A:1009735908398
21	Jain A , Dubes R . Algorithms for Clustering Data[M]. New Jersey: Prentice-Hall Inc, 1988.
22	Charikar M , Guha S . Improved combinatorial algorithms for the facility location[J]. SIAM Journal on Computing, 2005, 34, 803- 824. doi: 10.1137/S0097539701398594

[1]	周宇阳, 张惠珍, 马良. 求解应急医疗设施分层递进式选址问题的改进免疫算法[J]. 运筹学学报, 2021, 25(2): 15-34.
[2]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[3]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[4]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[5]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[6]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[7]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[8]	杨沐明, 黄亚魁, 戴彧虹. 一类多商品设施选址问题的基于线性松弛解的启发式方法[J]. 运筹学学报, 2019, 23(3): 15-26.
[9]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[10]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[11]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[12]	苗翠霞, 孟凡晓. 基于退化效应的两台机器流水作业可拒绝排序[J]. 运筹学学报, 2017, 21(2): 66-72.
[13]	徐大川, 许宜诚, 张冬梅. k-平均问题及其变形的算法综述[J]. 运筹学学报, 2017, 21(2): 101-109.
[14]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.
[15]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.

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

Squared metric facility location problem with outliers

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 22

相关文章 15

编辑推荐

Metrics

本文评价