中文

Operations Research Transactions >

2015 , Vol. 19 >Issue 2: 1 - 14

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

 Approximation algorithms for the  priority facility location problem with submodular penalties

Expand
  • 1. Department of Science, Taiyuan Institute of Technology, Taiyuan 030008,  China; 2. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China; 3. Department of Mathematics and Statistics, California State University, Long Beach, CA 90840, USA

Received date: 2014-12-01

  Online published: 2015-06-15

Fold

Abstract

In this paper, we study priority facility location problem with submodular penalties where each client has a level-of-service requirement. An open facility must satisfy the requirement of the clients served by it, and there is a submodular penalty cost corresponding with the unserved clients. The objective is to minimize the sum of the opening cost, the connection cost and the submodular penalty cost. We present the integer program, the linear programming relaxation and the dual program for the problem. Using the primal-dual and greedy augmentation techniques, we then propose two approximation algorithms and obtain the approximation ratios of 3 and 2.375 respectively.

Key words： submodular penalties; priority facility location; primal-dual; greedy augmentation; approximation algorithm

Cite this article

WANG Ying, WANG Fengmin, XU Dachuan, XU Wenqing .  Approximation algorithms for the  priority facility location problem with submodular penalties[J]. Operations Research Transactions, 2015 , 19(2) : 1 -14 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.02.001

References

Shmoys D B,  Tard\ddot{o}s \'{E}, Aardal K I. Approximation algorithms for facility location problems [C]//Proceedings of STOC, New York: ACM, 1997, 265-274.

Jain K, Mahdian M, Saberi A. A new greedy approach for facility location problems [C]// Proceedings of the 34th ACM Symposium on Theory of Computing, New York: Association for Computing Machinery, 2002, 731-740.

Li S. A 1.488 approximation algorithm for the uncapacitated facility location problem [C]//Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Part II, Springer, LNCS 6756, 2011, 77-88.


Jain K,  Vazirani V V. Primal-dual approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation [J]. Journal of the ACM, 2001, 48: 274-296.

Guha S,  Khuller S. Greedy strike back: Improved facility location algorithms [J]. Journal of Algorithms, 1999, 31: 228-248.

Charikar M, Guha S. Improved combinatorial algorithms for facility location problems [J]. SIAM Journal on Computing, 2005, 34: 803-824.

Charikar M, Khuller S, Mount D M, et al. Algorithms for facility location problems with outliers [C]// Proceedings of SODA, PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2001, 642-651.
Chudak F A,  Nagano K. Efficient solutions to relaxations of combinatorial problems  with submodular penalties via the lovasz extension and non-smooth convex optimization [C]//Proceedings of SODA, PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2007, 79-88.

Hayrapetyan A,  Swamy C,  Tard\ddot{o}s \'{E}. Network design for information networks [C]// Proceedings of SODA, PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2005, 933-942.

Fujishige S. Submodular Functions and Optimization [M]. Elsevier, 2005.

Du D L, Lu R X, Xu D C. A primal-dual approximation algorithm for the facility location problem with submodular penalties [J]. Algorithmica, 2012, 63: 191-200.

Li Y, Du D L, Xiu N H, et al. A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties [J]. Theoretical Computer Science, 2013, 476: 109-117.
Ravi R, Sinha A. Approximation algorithms for multicommodity facility location problems [J]. SIAM Journal on  Discrete Mathematics, 2010, 24: 538-551.

Mahdian M. Facility location and the analysis of algorithms through factor-revealing programs [D]. Massachusetts Institute of Technology, 2004.

Li G D, Wang Z, Wu C C. Approximation algorithms for the stochastic priority facility location problem [J]. Optimization, 2013, 62(7): 919-928.

Wang F M, Xu D C, Wu C C. Approximation algorithms for the priority facility location problem with penalties [J]. Journal of Systems Science and Complexity, 2014, DOI: 10.1007/s11424-014-2157-2.

Fleischer L, Iwata S. A push-relabel framework for submodular function minimization and applications to parametric optimization [J]. Discrete Applied Mathematics, 2003, 131: 311-322.

 
Options
Outlines

/

〈 〉