An improved per-scenario bound for the two-stage stochastic facility location problem

详细信息    查看全文

• 作者：ChenChen Wu (1) (3)
  DongLei Du (2)
  DaChuan Xu (3)
  
  1. College of Science ; Tianjin University of Technology ; Tianjin ; 300384 ; China
  3. Department of Applied Mathematics ; Beijing University of Technology ; Beijing ; 100124 ; China
  2. Faculty of Business Administration ; University of New Brunswick ; Fredericton ; NB ; E3B 5A3 ; Canada
  
• 关键词：facility location problem ; approximation algorithm ; LP ; rounding algorithm ; 90C27 ; 68W25
• 刊名：SCIENCE CHINA Mathematics
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：58
• 期：1
• 页码：213-220
• 全文大小：192 KB
• 参考文献：1. Byrka J, Aardal K. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J Comput, 2010, 39: 2212鈥?231 CrossRef
  2. Byrka J, Ghodsi M, Srinivasan A. LP-rounding algorithms for facility-location problems. ArXiv:1007.3611v2, 2012
  3. Chen X, Chen B. Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica, 2009, 53: 263鈥?97 453-007-9032-7" target="_blank" title="It opens in new window">CrossRef
  4. Chudak F A, Shmoys D B. Improved approximation algorithms for the uncapacitated facility location problem. SIAM J Comput, 2003, 33: 1鈥?5 405754" target="_blank" title="It opens in new window">CrossRef
  5. Li S.A1.488 approximation algorithm for the uncapacitated facility location problem. In: Proceedings of ICALP, Part II. Lecture Notes in Computer Science, vol. 6756. Berlin: Springer-Verlag, 2011, 77鈥?8
  6. Mahdian M. Facility location and the analysis of algorithms through factor-revealing programs. PhD Thesis. Cambridge: MIT, 2004
  7. Mahdian M, Ye Y, Zhang J. Approximation algorithms for metric facility location problems. SIAM J Comput, 2006, 36: 411鈥?32 435716" target="_blank" title="It opens in new window">CrossRef
  8. Shmoys D B, Swamy C. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J ACM, 2006, 53: 978鈥?012 45/1217856.1217860" target="_blank" title="It opens in new window">CrossRef
  9. Shmoys D B, Tardos 脡, Aardal K. Approximation algorithms for facility location problems (extended abstract). In: Proceedings of STOC. Berlin: Springer, 1998, 265鈥?74
  10. Shu J. An efficient greedy heuristic for warehouse-retailer network design optimization. Transpt Sci, 2010, 44: 183鈥?92 CrossRef
  11. Srinivasan A. Approximation algorithms for stochastic and risk-averse optimization. In: Proceedings of SODA. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2007, 1305鈥?313
  12. Swamy C. Approximation algorithms for clustering problems. PhD Thesis. Cornell: Cornell University, 2004
  13. Ravi R, Sinha A. Hedging uncertainty: Approximation algorithhms for stochastic optimization problems. Math Program, 2006, 108: 97鈥?14 CrossRef
  14. Ye Y, Zhang J. An approximation algorithm for the dynamic facility location problem. In: Combinatorial Optimization in Communication Networks. Kluwer: Kluwer Academic Publishers, 2005, 623鈥?37
  15. Zhang J. Approximating the two-level facility location problem via a quasi-greedy approach. Math Program, 2006, 108: 159鈥?76 4-x" target="_blank" title="It opens in new window">CrossRef
  16. Zhang J, Chen B, Ye Y. A multiexchange local search algorithm for the capacitated facility location problem. Math Oper Res, 2005, 30: 389鈥?03 40.0125" target="_blank" title="It opens in new window">CrossRef
  17. Zhang P. A new approximation algorithm for the / k-facility location problem. Theoret Comput Sci, 2007, 384: 126鈥?35 4" target="_blank" title="It opens in new window">CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Chinese Library of Science
  Applications of Mathematics
  
• 出版者：Science China Press, co-published with Springer
• ISSN：1869-1862

文摘

We study the two-stage stochastic facility location problem (2-SFLP) by proposing an LP (location problem)-rounding approximation algorithm with 2.3613 per-scenario bound for this problem, improving the previously best per-scenario bound of 2.4957.