删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

方度量的k层设施选址问题的近似算法

本站小编 Free考研考试/2021-12-27
方度量的k层设施选址问题的近似算法 邵嘉婷, 徐大川, 王凤敏北京工业大学应用数理学院, 北京 100124 Approximation Algorithms for the Squared Metric k-Level Facility Location Problem SHAO Jiating, XU Dachuan, WANG FengminDepartment of Information and Operations Research, College of Applied Sciences, Beijing University of Technology, Beijing 100124, China
摘要
图/表
参考文献(0)
相关文章(8)
点击分布统计
下载分布统计
-->

全文: PDF(408 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)
摘要本文中， 我们研究平方度量的k层设施选址问题， 该问题中设施分为k层， 每个顾客都要连接到位于不同层上的k个设施， 顾客与设施以及设施与设施之间的距离是平方度量的. 目标是使得开设费用与连接费用之和最小. 基于线性规划舍入技巧， 我们给出了9-近似算法. 进一步， 我们研究了平方度量的k层软容量设施选址问题， 并给出了线性规划舍入12.2216-近似算法.
服务
加入引用管理器
E-mail Alert
RSS
收稿日期: 2015-09-11
PACS:O221.7
基金资助:国家自然科学基金（11371001，11531014）资助项目.
引用本文:
邵嘉婷, 徐大川, 王凤敏. 方度量的k层设施选址问题的近似算法[J]. 应用数学学报, 2016, 39(4): 586-597. SHAO Jiating, XU Dachuan, WANG Fengmin. Approximation Algorithms for the Squared Metric k-Level Facility Location Problem. Acta Mathematicae Applicatae Sinica, 2016, 39(4): 586-597.
链接本文:
http://123.57.41.99/jweb_yysxxb/CN/或 http://123.57.41.99/jweb_yysxxb/CN/Y2016/V39/I4/586


[1] Shmoys D B, Tardö É, Aardal K I. Approximation Algorithms for Facility Location Problems. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 1997, 265-274
[2] Chudak F A, Shmoys D B. Improved Approximation Algorithms for the Uncapacitated Facility Location Problem. SIAM Journal on Computing, 2003, 33: 1-25
[3] Mahdian M, Markakis E, Saberi A, Vazirani V. A Greedy Facility Location Algorithm Ananlyzed Using Dual Fitting. In: Proceedings of Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 2001, 2129: 127-137
[4] Jain K, Mahdian M, Saberi A. A New Greedy Approach for Facility Location Problems. In: Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), 2002, 731-740
[5] Sviridenko M. An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. In: Proceedings of 9th International Integer Programming and Combinatorial Optimization Conference, 2002, 240-257
[6] Mahdian M, Ye Y, Zhang J. Improved Approximation Algorithms for Metric Facility Location Problems. Approximation Algorithms for Combinatorial Optimization, 2002, 229-242
[7] Li S. A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), Part I!I, 2011, 77-88
[8] Guha S, Khuller S. Greedy Strike Back: Improved Facility Location Algorithms. Journal of Algorithms, 1999, 31: 228-248
[9] Sviridenko M. Cited as Personal Communication in
[5] , July, 1998
[10] Jain K, Vazirani V V. Primal Dual Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation. Journal of the ACM, 2001, 48: 274-296
[11] Fernandes C G, Meira L A A, Miyazawa F K, Pedrosa L L C. A Systematic Approach to Bound Factor-Revealing Lps and Its Application to the Metric and Squared Metric Facility Location Problems. Mathematical Programming, 2014, Available from: http://dx.doi.org/10.1007/s10107-014-0821-x
[12] Wang Y, Xu D, Du D, Wu C. An Approximation Algorithm for Squared Metric Facility Location Problems with Linear Penalties. to appear in Optimization Letters
[13] Li Y, Du D, Xiu N, Xu D. Improved Approximation Algorithms for the Facility Location Problems with Linear/Submodular Penalties. Algorithmica, 2014, Available from: http://dx.doi.org/10.1007/s00453-014-9911-7
[14] Aardal K, LabbéM, Leung J, Queyranne M. On the Two-Level Uncapacitated Facility Location Problem. INFORMS Journal on Computing, 1996, 8: 289-301
[15] Kaufman L, Vanden Eede M, Hansen P. A Plant and Warehouse Location Problem. Operational Research Quarterly, 1977, 28: 547-557
[16] Tcha D, Lee B. A Branch-and-Bound Algorithm for the Multi-Level Uncapacitated Location Problem. European Journal of Operational Research, 1984, 18: 35-43
[17] Van Roy T J, Erlenkotter D. A Dual Based Procedure for Dynamic Facility Location. Management Science, 1982, 28: 1091-1105
[18] Zhang J. Approximating the Two-Level Facility Location Problem via a Quasi-Greedy Approach. Mathematical Programming, 2006, 108: 159-176
[19] Ageev A, Ye Y, Zhang J. Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem. SIAM Journal on Discrete Mathematics, 2004, 18: 207-217
[20] Aardal K, Chudak F A, Shmoys D B. A 3-Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem. Information Processing Letters, 1999, 72: 161-167
[21] Wu C, Xu D. An Improved Approximation Algorithm for the k-Level Facility Location Problem with Soft Capacities, to appear in Acta Mathematicae Applicatae Sinica (English Series).
[22] Bumb A, Kern W. A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem, In: Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, 2001, 55-62

[1]黎煜, 徐大川. 带次模惩罚的仓库—零售商网络设计问题的近似算法[J]. 应用数学学报(英文版), 2012, (2): 309-320.
[2]罗文昌, 李剑秋. 关于单机两个客户竞争排序问题1‖∑wjAcjA: fmaxB≤Q的一个注记[J]. 应用数学学报(英文版), 2011, 34(1): 73-80.
[3]徐大川, 韩继业, 杜东雷. 关于图划分问题的改进的近似算法[J]. 应用数学学报(英文版), 2005, 28(4): 587-597.
[4]陈祥伟. 平行机中关于关于同类机近似算法的研究[J]. 应用数学学报(英文版), 2004, 27(4): 599-607.
[5]苏纯洁. 带服务器的三台平行机排序问题的复杂性和近似算法[J]. 应用数学学报(英文版), 2003, 26(3): 544-550.
[6]李国君, 张少强, Ousmane Samake, 陈光亭. 环形全光WDM网络的波长分配[J]. 应用数学学报(英文版), 2003, 26(3): 427-433.
[7]谈之奕, 何勇. 带机器准备时间的平行机ordinal排序及近似算法[J]. 应用数学学报(英文版), 2002, 25(2): 223-229.
[8]何勇. Q_2‖C_(max)的对偶近似算法[J]. 应用数学学报(英文版), 1999, 22(1): 123-129.



PDF全文下载地址:

http://123.57.41.99/jweb_yysxxb/CN/article/downloadArticleFile.do?attachType=PDF&id=14178
相关话题/应用数学 网络 统计 设计 北京工业大学

Free考研考试FreeKaoYan.Com
欢迎来到Free考研考试，"为实现人生的Free而奋斗"

© 2020 FreeKaoYan! . All rights reserved.