Approximation algorithms for the priority facility location problem with penalties

1. Shmoys D B, Tardos É, and Aardal K I, Approximation algorithms for facility location problems, Proceedings of STOC, 1997, 265–274.

   Google Scholar 

2. Li S, A 1.488-approximation algorithm for the uncapacitated facility location problem, Proceedings of ICALP, Part II, 2011, 77–88.

   Google Scholar 

3. Guha S and Khuller S, Greedy strikes back: Improved facility location algorithms, Proceedings of SODA, 1998, 649–657.

   Google Scholar 

4. Ageev A, Ye Y, and Zhang J, Improved combinatorial approximation algorithms for the k-level facility location problem, SIAM J. Discrete Math., 2003, 18: 207–217.

   Article  MathSciNet  Google Scholar 

5. Charikar M and Guha S, Improved combinatorial algorithms for facility location problems, SIAM J. Comput., 2005, 34: 803–824.

   Article  MathSciNet  MATH  Google Scholar 

6. Zhang J, Chen B, and Ye Y, A multiexchange local search algorithm for the capacitated facility location problem, Math. Oper. Res., 2005, 30: 389–403.

   Article  MathSciNet  MATH  Google Scholar 

7. Zhang J, Approximating the two-level facility location problem via a quasi-greedy approach, Math. Program., 2006, 108: 159–176.

   Article  MathSciNet  MATH  Google Scholar 

8. Zhang P, A new approximation algorithm for the k-facility location problem, Theor. Comput. Sci., 2007, 384: 126–135.

   Article  MATH  Google Scholar 

9. Chen X and Chen B, Approximation algorithms for soft-capacitated facility location in capacitated network design, Algorithmica, 2009, 53: 263–297.

   Article  MathSciNet  MATH  Google Scholar 

10. Du D, Wang X, and Xu D, An approximation algorithm for the k-level capacitated facility location problem, J. Comb. Optim., 2010, 20: 361–368.

    Article  MathSciNet  MATH  Google Scholar 

11. Shu J, An efficient greedy heuristic for warehouse-retailer network design optimization, Transport. Sci., 2010, 44: 183–192.

    Article  Google Scholar 

12. Du D, Lu R, and Xu D, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Algorithmica, 2012, 63: 191–200.

    Article  MathSciNet  MATH  Google Scholar 

13. Charikar M, Khuller S, Mount D M, and Narasimhan G, Algorithms for facility location problems with outliers, Proceedings of SODA, 2001, 642–651.

    Google Scholar 

14. Xu G and Xu J, An LP-rounding algorithm for approximating uncapacitated facility location problem with penalties, Inform. Process. Lett., 2005, 94: 119–123.

    Article  MathSciNet  MATH  Google Scholar 

15. Xu G and Xu J, An improved approximation algorithm for uncapacitated facility location problem with penalties, J. Comb. Optim., 2008, 17: 424–436.

    Article  Google Scholar 

16. Hayrapetyan A, Swamy C, and Tardos É, Network design for information networks, Proceedings of SODA, 2005, 933–942.

    Google Scholar 

17. Chudak F A and Nagano K, Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization, Proceedings of SODA, 2007, 79–88.

    Google Scholar 

18. Ravi R and Sinha A, Multicommodity facility location, Proceedings of SODA, 2004, 342–349.

    Google Scholar 

19. Mahdian M, Facility location and the analysis of algorithms through factor-revealing problems, Ph.D.’s degree thesis, Massachusetts Institute of Technology, Cambridge, MA, 2004.

    Google Scholar 

20. Li G, Wang Z, and Wu C, Approximation algorithms for the stochastic priority facility location problem, Optimization, 2013, 62(7): 919–928.

    Article  MathSciNet  MATH  Google Scholar 

21. Jain K and Vazirani V V, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, J. ACM, 2001, 48: 274–296.

    Article  MathSciNet  MATH  Google Scholar 

Download references