Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (1): 117-126.

• Original Articles • Previous Articles    

Bicriteria approximation algorithms for the lower-bounded facility location problem with penalties and soft-capacity

LI Gaidi1, WANG Zhen1, WU Yulin   

  1. 1. Department of Applied Mathematics, Beijing University of Technology
  • Online:2013-03-15 Published:2013-03-15

Abstract: We study the lower-bounded facility location problem with penalties (LBFLP) and the soft-capacity LBFLP. For the LBFLP, we present an updated bicriteria approximation algorithm which maintains the same performance factor ρ(1+α)/(1-α)  as that for the problem without penalties  in Hierarchical placement and network design problems(Guha S, Meyerson  A, Munagala K. Hierarchical placement and network design problems [C]//Proceedings of Foundations of Computer Science, 2000: 892328, DOI:  10.1109/SFCS.2000.892328)and Building steiner trees with incomplete global knowledge(Karger D R,  Minkoff  M. Building steiner trees with incomplete global knowledge [C]//Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329). We further extend this result to the soft-capacitated LBFLP and achieve a performance factor twice as much as that for LBFLP.

Key words: lower-bounded facility location, approximation algorithm, bicriteria algorithm