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

An approximation algorithm for the squared metric dynamic facility location problem

研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题.研究中首先利用原始对偶技巧得到9-近似算法,然后利用贪婪增广技巧将近似比改进到2.606,最后讨论了该问题的相应变形问题.

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.