平方度量动态设施选址问题的近似算法

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

Operations Research Transactions ›› 2018, Vol. 22 ›› Issue (3): 49-58.doi: 10.15960/j.cnki.issn.1007-6093.2018.03.005

Previous Articles Next Articles

An approximation algorithm for the squared metric dynamic facility location problem

JIANG Yanjun¹XU Dachuan¹ZHANG Dongmei^2,*

1. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China; 2. School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, China

Received:2017-11-02 Online:2018-09-15 Published:2018-09-15

Abstract

Abstract:

We consider a generalization of the classic single-period metric facility location problem, which is the squared metric dynamic facility location problem. We utilize the primal-dual scheme to design a 9-approximation algorithm. Then the approximation ratio is improved to 2.606 by the greedy improvement technique. We also give some discussion for several variants of the squared metric dynamic facility location problem in future work.

Key words: facility location problem, approximation algorithm, NP-hard

JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem[J]. Operations Research Transactions, 2018, 22(3): 49-58.

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.2018.03.005

https://www.ort.shu.edu.cn/EN/Y2018/V22/I3/49

[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]	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.
[3]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[12]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[13]	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.
[14]	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.
[15]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.

An approximation algorithm for the squared metric dynamic facility location problem

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments