中文

Operations Research Transactions >

2018 , Vol. 22 >Issue 3: 49 - 58

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2018.03.005

An approximation algorithm for the squared metric dynamic facility location problem

Expand
  • 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 date: 2017-11-02

  Online published: 2018-09-15

Fold

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

Cite this article

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

Options
Outlines

/

〈 〉