An approximation framework for bounded facility location problems

Wenchang Luo, Bing Su, Yao Xu, Guohui Lin

Research output: Contribution to book or proceedingConference articlepeer-review

Abstract

We study the bounded metric uncapacitated facility location (bUFL) problem and its two variants, the bounded fault-tolerant facility location (bFTFL) problem and the bounded fault-tolerant facility placement (bFTFP) problem. We propose a unified approximation framework built on the state-of-the-art approximation algorithms for the three unbounded counterparts, leading to a (2.488 + ε) -approximation algorithm for the bUFL problem in the Euclidean plane, a (1.488+H(n)) -approximation algorithm for the bUFL problem, a (1.725+H(n)) -approximation algorithm for the bFTFL problem, and a (1.515+H(n)) -approximation algorithm for the bFTFP problem in a general metric space. We also prove an inapproximability result for all the three bounded facility location problems in a general metric space.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
EditorsDaming Zhu, Lusheng Wang
PublisherSpringer Verlag
Pages353-364
Number of pages12
ISBN (Print)9783319947754
DOIs
StatePublished - 2018
Event24th International Conference on Computing and Combinatorics Conference, COCOON 2018 - Qing Dao, China
Duration: Jul 2 2018Jul 4 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10976 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Conference on Computing and Combinatorics Conference, COCOON 2018
Country/TerritoryChina
CityQing Dao
Period07/2/1807/4/18

Keywords

  • Approximation algorithm
  • Bounded uncapacitated facility location
  • Weighted dominating set in unit disk graphs
  • Weighted set multi-cover

Fingerprint

Dive into the research topics of 'An approximation framework for bounded facility location problems'. Together they form a unique fingerprint.

Cite this