Approximation algorithm for facility location with service installation costs

Dachuan Xu, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

In this paper, we study the uncapacitated facility location problem with service installation costs depending on the type of service required. We propose a polynomial-time approximation algorithm with approximation ratio 1.808 which improves the previous approximation ratio of 2.391 of Shmoys, Swamy, and Levi.

Original languageEnglish (US)
Pages (from-to)46-50
Number of pages5
JournalOperations Research Letters
Volume36
Issue number1
DOIs
StatePublished - Jan 2008

Bibliographical note

Funding Information:
We are grateful to Jiawei Zhang for helpful discussions and comments, and we would also like to thank the referee for the insightful comments. This work was done while the first author was a visiting scholar at the Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, Hong Kong. The first author's research was supported by NSF of China (Grant no. 10401038) and Startup grant for doctoral research of Beijing University of Technology. The second author's research was supported by Hong Kong RGC Earmarked Grant CUHK418406.

Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

Keywords

  • Approximation algorithm
  • Facility location
  • Linear programming relaxation

Fingerprint

Dive into the research topics of 'Approximation algorithm for facility location with service installation costs'. Together they form a unique fingerprint.

Cite this