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

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

Operations Research Transactions

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, doi: 10.15960/j.cnki.issn.1007-6093.2018.03.005.

[1]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[3]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[4]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[5]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[6]	YANG Muming, HUANG Yakui, DAI Yuhong. Linear relaxation solution based heuristics for a class of multi-product facility location problems [J]. Operations Research Transactions, 2019, 23(3): 15-26.
[7]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[8]	MIAO Cuixia, MENG Fanxiao. Two-machine flow-shop scheduling with deterioration and rejection [J]. Operations Research Transactions, 2017, 21(2): 66-72.
[9]	ZHANG Long. Two-stage supply chain scheduling with a limited holding time [J]. Operations Research Transactions, 2017, 21(2): 126-134.
[10]	XU Dachuan, XU Yicheng, ZHANG Dongmei. A survey on algorithms for k-means problem and its variants [J]. Operations Research Transactions, 2017, 21(2): 101-109.
[11]	CHEN Guangting, CHEN Lei, ZHANG An, CHEN Yong. Approximation algorithms for two-machine flow shop scheduling with an outsourcing option [J]. Operations Research Transactions, 2016, 20(4): 109-114.
[12]	ZHONG Weiya, MA Xiaoru. A no-wait flowshop scheduling problem with processing flexibility and transportation [J]. Operations Research Transactions, 2016, 20(4): 93-101.
[13]	SUN Ting, LI Gaidi, XU Wenqing. Approximation algorithms for max cut and max bisection problems using semi-definite programming relaxations [J]. Operations Research Transactions, 2016, 20(3): 21-32.
[14]	FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties [J]. Operations Research Transactions, 2016, 20(2): 69-78.
[15]	YAN Lincheng,XIAO Han,ZHAO Hongjuan,SUN Xiaoqi. An approximation algorithm for reliable facility location problem [J]. Operations Research Transactions, 2015, 19(4): 14-24.

An approximation algorithm for the squared metric dynamic facility location problem

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments