平方度量动态设施选址问题的近似算法
|
摘要
研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题.研究中首先利用原始对偶技巧得到9-近似算法,然后利用贪婪增广技巧将近似比改进到2.606,最后讨论了该问题的相应变形问题.
We consider a generalization of the classic single-period metric facility location problem,which is the squared metric dynamic facility location problem. We utilize the primal-dual scheme to design a 9-approximation algorithm. Then the approximation ratio is improved to 2.606 by the greedy improvement technique. We also give some discussion for several variants of the squared metric dynamic facility location problem in future work.
We consider a generalization of the classic single-period metric facility location problem,which is the squared metric dynamic facility location problem. We utilize the primal-dual scheme to design a 9-approximation algorithm. Then the approximation ratio is improved to 2.606 by the greedy improvement technique. We also give some discussion for several variants of the squared metric dynamic facility location problem in future work.
引文
[1]Vazirani V V.Approximation Algorithms[M].Berlin:Springer-Verlag,2001.
[2]Shmoys D,Tard(o|¨)s E,Aardal K.Approximation algorithm for facility location problems[C]//Proceedings of the 29th Annual ACM Symposium on Theory of Computing,1997,265-274.
[3]Williamson D P,Shmoys D B.The Design of Approximation Algorithms[M].Cambrige:Cambridge University Press,2011.
[4]Hochbaum D S.Heuristics for the fixed cost median problem[J].Mathematical Programming,1982,22:148-162.
[5]Chudak F A,Shmoys D B.Improved approximation algorithms for the uncapacitated facility location problem[J].SIAM Journal on Computing,2003,33:1-25.
[6]Jain K,Vazirani V V.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.
[7]Korupolu M R,Plaxton C G,Rajaraman R.Analysis of a local search heuristic for facility location problems[J].Journal of Algorithms,2000,37:146-188.
[8]Byrka J,Aardal K.An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem[J].SIAM Journal on Computing,2010,39:2212-2231.
[9]Li S.A 1.488 approximation algorithm for the uncapacitated facility location problem[J].Information and Computation,2013,222:45-58.
[10]Guha S,Khuller S.Greedy strikes back:improved facility location algorithms[J].Journal of Algorithms,1999,31:228-248.
[11]Vygen J.Approximation Algorithms for Facility Location Problems[M].Technical Report05950-OR,Research Institute for Discrete Mathematics,University of Bonn,2005.
[12]Ye Y,Zhang J.An approximation algorithm for the dynamic facility location problem[M]//Combinatorial Optimization in Communication Networks,New York:Kluwer Academic Publishers,2005,623-637.
[13]姜春艳,徐大川.带惩罚的动态设施选址问题的近似算法[J].应用数学学报,2009,32:988-996.
[14]Jiang Y,Xu D,Du D,et al.An approximation algorithm for the dynamic facility location problem with outliers[J].Optimization Letters.2017,DOI:10.1007/s11590-017-1153-6.
[15]Charika M,Guha E,Shmoys D.A constant-factor approximation algorithm for the k-median problem[C]//Proceedings of the 31st Annual ACM Symposium on Theory of Computing,1999,1-10.
[16]Mangasarian O L.Mathematical programming in data mining[J].Data Mining and Knowledge Discovery,1997,1:183-201.
[17]Jain A K,Dubes R C.Algorithms for Clustering Data[M].Prentice-Hall,Inc.,1988.
[18]Fernandes C G,Meira L A,Miyazawa F K,et al.A systematic approach to bound factorrevealing LPs and its application to the metric and squared metric facility location problems[J].Mathematical Programming,2015,153:655-685.
[19]Charikar M,Guha S.Improved combinatorial algorithms for the facility location[J].SIAM Journal on Computing,2005,34:803-824.
[2]Shmoys D,Tard(o|¨)s E,Aardal K.Approximation algorithm for facility location problems[C]//Proceedings of the 29th Annual ACM Symposium on Theory of Computing,1997,265-274.
[3]Williamson D P,Shmoys D B.The Design of Approximation Algorithms[M].Cambrige:Cambridge University Press,2011.
[4]Hochbaum D S.Heuristics for the fixed cost median problem[J].Mathematical Programming,1982,22:148-162.
[5]Chudak F A,Shmoys D B.Improved approximation algorithms for the uncapacitated facility location problem[J].SIAM Journal on Computing,2003,33:1-25.
[6]Jain K,Vazirani V V.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.
[7]Korupolu M R,Plaxton C G,Rajaraman R.Analysis of a local search heuristic for facility location problems[J].Journal of Algorithms,2000,37:146-188.
[8]Byrka J,Aardal K.An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem[J].SIAM Journal on Computing,2010,39:2212-2231.
[9]Li S.A 1.488 approximation algorithm for the uncapacitated facility location problem[J].Information and Computation,2013,222:45-58.
[10]Guha S,Khuller S.Greedy strikes back:improved facility location algorithms[J].Journal of Algorithms,1999,31:228-248.
[11]Vygen J.Approximation Algorithms for Facility Location Problems[M].Technical Report05950-OR,Research Institute for Discrete Mathematics,University of Bonn,2005.
[12]Ye Y,Zhang J.An approximation algorithm for the dynamic facility location problem[M]//Combinatorial Optimization in Communication Networks,New York:Kluwer Academic Publishers,2005,623-637.
[13]姜春艳,徐大川.带惩罚的动态设施选址问题的近似算法[J].应用数学学报,2009,32:988-996.
[14]Jiang Y,Xu D,Du D,et al.An approximation algorithm for the dynamic facility location problem with outliers[J].Optimization Letters.2017,DOI:10.1007/s11590-017-1153-6.
[15]Charika M,Guha E,Shmoys D.A constant-factor approximation algorithm for the k-median problem[C]//Proceedings of the 31st Annual ACM Symposium on Theory of Computing,1999,1-10.
[16]Mangasarian O L.Mathematical programming in data mining[J].Data Mining and Knowledge Discovery,1997,1:183-201.
[17]Jain A K,Dubes R C.Algorithms for Clustering Data[M].Prentice-Hall,Inc.,1988.
[18]Fernandes C G,Meira L A,Miyazawa F K,et al.A systematic approach to bound factorrevealing LPs and its application to the metric and squared metric facility location problems[J].Mathematical Programming,2015,153:655-685.
[19]Charikar M,Guha S.Improved combinatorial algorithms for the facility location[J].SIAM Journal on Computing,2005,34:803-824.