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

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

Abstract

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

CLC Number:

O221.7

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

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2021.01.011

https://www.ort.shu.edu.cn/EN/Y2021/V25/I1/114

Figures/Tables 3

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]	WU Hongyi, WANG Dong, WAN Long, LUO Wenchang. Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions [J]. Operations Research Transactions, 2026, 30(1): 188-196.
[2]	Ling GAI, Weiwei ZHANG, Minming LI. Mechanism design and analysis for facility location bin packing games [J]. Operations Research Transactions, 2025, 29(2): 58-67.
[3]	Hao LIN, Cheng HE. Minimum branch spanning tree problem and its applications to the location problems [J]. Operations Research Transactions, 2025, 29(2): 103-112.
[4]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[5]	Zilan YANG, Juanping ZHU, Yu YANG. The expansion problem of maximum capacity spanning arborescence in networks [J]. Operations Research Transactions, 2024, 28(2): 151-158.
[6]	Tingying WU, Yao WANG, Zhili ZHOU, Yating REN. A two-echelon facility location problem with choice of facility size [J]. Operations Research Transactions, 2023, 27(3): 83-95.
[7]	Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection [J]. Operations Research Transactions, 2023, 27(3): 137-149.
[8]	Chenghao ZHOU, Boxuan LYU, Hanyu ZHOU, Haiyan LU. Optimization model and algorithm for Online to Offline dynamic take-out delivery routing problem centered on business districts [J]. Operations Research Transactions, 2022, 26(3): 17-30.
[9]	An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN. Maximum matching based approximation algorithms for precedence constrained scheduling problems [J]. Operations Research Transactions, 2022, 26(3): 57-74.
[10]	Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[11]	Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection [J]. Operations Research Transactions, 2022, 26(2): 73-82.
[12]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[13]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[14]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[15]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.

Squared metric facility location problem with outliers

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

Related Articles 15

Recommended Articles

Metrics

Comments