A primal-dual approximation algorithm for stochastic facility location problem with service installation costs

+ 作者地址

  • 摘要
  • 参考文献
  • 相关文章
  • 统计
We consider the stochastic version of the facility location problem with service installation costs.Using the primal-dual technique,we obtain a 7-approximation algorithm.

[1] Ageev A;Ye Y;Zhang J .Improved combinatorial approximation algorithms for the k-level facility location problem[J].SIAM Journal on Discrete Mathematics,2004,18:207-217.

[2] Byrka, J.;Aardal, K. .An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem[J].SIAM Journal on Computing,2010(6):2212-2231.

[3] Chen X;Chen B .Approximation algorithms for soft-capacitated facility location in capacitated network design[J].Algorithmica,2009,53:263297.

[4] Du D;Lu R;Xu D.A primal-dual approximation algorithm for the facility location problem with submodular penalties[J].Algorithmica

[5] Du, D.;Wang, X.;Xu, D. .An approximation algorithm for the k-level capacitated facility location problem[J].Journal of combinatorial optimization,2010(4):361-368.

[6] Guha S;Khuller S .Greedy strike back:improved facility location algorithms[J].Journal of Algorithms,1999,31:228248.

[7] KAMAL JAIN;MOHAMMAD MAHDIAN;EVANGELOS MARKAKIS;AMIN SABERI;VIJAY V. VAZIRANI .Greedy Facility Location Algorithms Analyzed Using Dual Fitting with Factor-Revealing LP[J].Journal of the ACM,2003(6):795-824.

[8] KAMAL JAIN;VIJAY V. VAZIRANI .Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation[J].Journal of the ACM,2001(2):274-296.

[9] Li S.A 1.488-approximation algorithm for the uncapacitated facility location problem[A].,2011:77-88.

[10] Mahdian M;Ye YY;Zhang JW .Approximation algorithms for metric facility location problems[J].SIAM Journal on Computing,2006(2):411-432.

[11] Ravi R;Sinha A .Hedging uncertainty: Approximation algorithms for stochastic optimization problems[J].Mathematical Programming,2006(1):97-114.

[12] Shmoys D B;Swamy C;Levi R.Facility location with service installation costs[A].,2004:1081-1090.

[13] Shmoys D B;Tard(o)s E;Aardal K I.Approximation algorithms for facility location problems (extended abstract)[A].,1997:265-274.

[14] Jia Shu .An Efficient Greedy Heuristic for Warehouse-Retailer Network Design Optimization[J].Transportation science,2010(2):183-192.

[15] Shu J;Teo CP;Shen ZJM .Stochastic transportation-inventory network design problem[J].Operations Research: The Journal of the Operations Research Society of America,2005(1):48-60.

[16] Wang, Z.;Du, D.;Gabor, A.F.;Xu, D. .An approximation algorithm for the κ-level stochastic facility location problem[J].Operations Research Letters: A Journal of the Operations Research Society of America,2010(5):386-389.

[17] Wang Z;Du D;Xu D.A primal-dual approximation algorithm for the k-level stochastic facility location problem[A].,2010:253-260.

[18] Xu D;Zhang S .Approximation algorithm for facility location problems with service installation costs[J].Oper Rcs Lett,2008,36:46-50.

[19] Ye Y;Zhang J.An approximation algorithm for the dynamic facility location problem[A].Dordrecht:kluwer Academic Publishers,2005:623-637.

[20] Zhang JW .Approximating the two-level facility location problem via a quasi-greedy approach[J].Mathematical Programming,2006(1):159-176.

[21] Zhang JW;Chen B;Ye YY .A multiexchange local search algorithm for the capacitated facility location problem[J].Mathematics of operations research,2005(2):389-403.

[22] Zhang P .A new approximation algorithm for the k-facility location problem[J].Theoretical computer science,2007(1):126-135.

DOI: http://dx.doi.org/10.1007/sl1464-011-0153-6

语种: 英文   

基金The authors would like to thank two anonymous referees for...

  • + 更多
  • 字体大小