A per-scenario bound for the two-stage stochastic facility location problem with linear penalty

References

• ShmoysDB, TardösE, Aardal. KIApproximation algorithms for facility location problems. Proceedings of STOC; 1997. p. 265–274.
   Google Scholar
• XuD, GaoD, WuC. A 3-approximation algorithm for the stochastic facility location problem with submodular penalties. Optimization.in press. doi:10.1080/02331934.2013.793326.
   Google Scholar
• JainK, MahdianM, MarkakisE, SaberiA, VaziraniVV. Greedy facility location algorithm analyzed using dual fitting with factor-revealing LP. J. ACM.2003;50:795–824.
   Web of Science ®Google Scholar
• MahdianM, YeY, ZhangJ. Approximation algorithms for metric facility location problems. SIAM J. Comput.2006;36:411–432.
   Web of Science ®Google Scholar
• LiS. A 1.488 approximation algorithm for the uncapacitated facility location problem. Inform. Computat.2013;222:45–58.
   Web of Science ®Google Scholar
• CharikarM, KhullerS, MountDM, NaraasimbanG. Algorithms for facility location problems with outliers. Proceedings of SODA; 2001. p. 642–651.
   Google Scholar
• XuG, XuJ. An LP rounding algorithm for approximating uncapacitated facility location problem with penalty. Inform. Process. Lett.2005;94:119–123.
   Web of Science ®Google Scholar
• GeunesJ, LeviR, RomeijnHE, ShmoysDB. Approximation algorithms for supply chain planning and logistics problems with market choice. Math. Program.2011;130:85–106.
   Web of Science ®Google Scholar
• XuG, XuJ. An improved approximation algorithm for uncapacitated facility location problem with penalty. J. Comb. Optim.2008;17:424–436.
   Web of Science ®Google Scholar
• ChudakFA, NaganoK. Efficient solutions to relaxations of combinatorial problems with submodular penalty via the Lovász extension and non-smooth convex optimization.Proceedings of SODA; 2007. p. 79–88.
   Google Scholar
• DuD, LuR, XuD. A primal-dual approximation algorithm for the facility location problem with submodular penalty. Algorithmica. 2012;63:191–200.
   Web of Science ®Google Scholar
• HayrapetyanA, SwamyC, TardösE. Network design for information networks. Proceedings of SODA; 2005. p. 933–942.
   Google Scholar
• LiY, DuD, XiuN, XuD. A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties. Theoretical Comput. Sci.2013;476:109–117.
   Web of Science ®Google Scholar
• LiY, DuD, XiuN, XuD. Improved approximation algorithms for the facility location problems with linear/submodular penalty.Proceedings of COCOON; 2013. p. 292–303.
   Google Scholar
• AgeevA, YeY, ZhangJ. Improved combinatorial approximation algorithms for the k-level facility location problem. SIAM J. Discrete Math.2004;18:207–217.
   Web of Science ®Google Scholar
• ChenX, ChenB. Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica. 2007;53:263–297.
   Web of Science ®Google Scholar
• ShuJ. An efficient greedy heuristic for warehouse-retailer network design optimization. Transport. Sci.2010;44:183–192.
   Web of Science ®Google Scholar
• ShuJ, TeoCP, Max ShenZJ. Stochastic transportation-inventory network design problem. Oper. Res.2005;53:48–60.
   Web of Science ®Google Scholar
• WangZ, DuD, GaborAF, XuD. An approximation algorithm for the k-level stochastic facility location problem. Oper. Res. Lett.2010;38:386–389.
   Web of Science ®Google Scholar
• ZhangJ. Approximating the two-level facility location problem via a quasi-greedy approach. Math. Program.2006;108:159–176.
   Web of Science ®Google Scholar
• ZhangJ, ChenB, YeY. A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res.2005;30:389–403.
   Web of Science ®Google Scholar
• ZhangP. A new approximation algorithm for the k-facility location problem. Theor. Comput. Sci.2007;384:126–135.
   Web of Science ®Google Scholar
• RaviR, SinhaA. Hedging uncertainty: approximation algorithhms for stochastic optimization problems. Math. Program.2006;108:97–114.
   Web of Science ®Google Scholar
• YeY, ZhangJ. An approximation algorithm for the dynamic facility location problem. In Combinatorial optimization in communication networks. Kluwer Academic. 2005 p. 623–637
   Google Scholar
• SwamyC. Approximation algorithms for clustering problems [Ph.D. thesis]. Cornell University; 2004.
   Google Scholar
• SrinivasanA. Approximation algorithms for stochastic and risk-averse optimization. Proceedings of SODA; 2007. p. 1305–1313.
   Google Scholar
• ByrkaJ, GhodsiM, SirnivasanA. LP-rounding algorithms for facility-location problems. 2012. arXiv:1007.3611v2. Available from: http://arxiv.org/abs/1007.3611
   Google Scholar
• WuC, DuD, XuD. An improved per-scenario bound for the two-stage stochastic facility location problem [Working paper]. Beijing University of Technology; 2013.
   Google Scholar
• ChudakFA, ShmoysDB. Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput.2003;33:1–25.
   Web of Science ®Google Scholar
• SviridenkoM. An improved approximation algorithm for the metric uncapacitated facility location problem. Proceedings of IPCO; 2002. p. 240–257.
   Google Scholar