双会议服务器选址问题研究

doi:10.12005/orms.2022.0277

运筹与管理 ›› 2022, Vol. 31 ›› Issue (9): 1-6.DOI: 10.12005/orms.2022.0277

• 理论分析与方法探讨 • 下一篇

双会议服务器选址问题研究

徐弈¹, 陈莹²

1.西安理工大学经济与管理学院,陕西西安 710054;
2.西安交通大学管理学院,陕西西安 710049

收稿日期:2019-08-22 出版日期:2022-09-25 发布日期:2022-10-21
作者简介:徐弈(1989-),男,陕西省西安市人,讲师,理学博士,研究方向为:优化算法设计;陈莹(1989-),女,满族,辽宁省锦州市人,博士研究生,研究方向为:优化算法设计。
基金资助:
陕西省自然科学基础研究计划资助项目(2020JQ-654);陕西省教育厅自然专项(17JK0539);西安理工大学校博士启动金(105-451119001)

Double Conference Servers Location Problem

XU Yi¹, CHEN Ying²

1. School of Economics and Management, Xi'an University of Technology, Xi'an 710054, China;
2. School of Management, Xi'an Jiaotong University, Xi'an 710049, China

Received:2019-08-22 Online:2022-09-25 Published:2022-10-21

摘要/Abstract

摘要： 中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n³logn)。

关键词: 选址问题, 2中位问题, 韦伯问题, 组合优化

Abstract: The median location problem is always a hot issue in management science. In this paper, we consider the double conference servers location problem. Let P be a set of n points in the plane. The double conference servers location problem is to find a dipolar spanning tree spans P and minimize the sum of the distance among all pairs of leaves on this tree. In this paper, we show the key geometry structure and propose the exact algorithm which solves this problem in time.

Key words: facility location problem, 2-median problem, Weber problem, combinatorial optimization

中图分类号:

TB114.1

徐弈, 陈莹. 双会议服务器选址问题研究[J]. 运筹与管理, 2022, 31(9): 1-6.

XU Yi, CHEN Ying. Double Conference Servers Location Problem[J]. Operations Research and Management Science, 2022, 31(9): 1-6.

参考文献

[1] Minieka E. The centers and medians of a graph[J]. Operations Research, 1977, 25(4): 641-650.
[2] Garfinkel R S, Neebe A W, Rao M R. The m-center problem: Minimaxfacality location[J]. Management Science, 2011, 23(10): 1133-1142.
[3] Tansel B C, Francis R L, Lowe T J. State of the art—location on networks: a survey. part I: the p-center and p-median problems[J]. Management science, 1983, 29(4): 482-497.
[4] Wang H, Zhang J. Line-constrained k-median, k-means, and k-center problems in the plane[J]. Algorithms and Computation, 2014: 3-14.
[5] Hwang R, Lee R, Chang R. The slab dividing approach to solve the euclidean p-center problem[J]. Algorithmica, 1993, 9(1): 1-22.
[6] Wang H, Zhang J. An $O(n＼log_{}n)$-time algorithm for the k-center problem in trees[C]. In: Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018), 2018, 72: 1-15.
[7] Fowler R J, Paterson M S, Tanimoto S L. Optimal packing and covering in the plane are NP-complete[J]. Information Processing Letters, 1981, 12(3): 133-137.
[8] Elloumi S, Labbe M, Pochet Y. A new formulation and resolution method for the p-center problem[J]. Informs Journal on Computing, 2004, 16(1): 84-94.
[9] Minieka E. The centers and medians of a graph[J]. Operations Research, 1977, 25(4): 641-650.
[10] Lin G, Xue G. K-center and k-median problems in graded distances[J]. Theoretical computer science, 1998, 207(1): 181-192.
[11] Halfin S. On finding the absolute and vertex centers of a tree with distances[J]. Transportation Science, 1974, 8(1): 75-77.
[12] Du H, Xu Y. An approximation algorithm for k-center problem on a convex polygon[J]. Journal of Combinatorial Optimization, 2014, 27(3): 504-518.
[13] Xu Y, Peng J, Xu Y. The mixed center location problem[J]. Journal of Combinatorial Optimization, 2018, 36(4): 1128-1144.
[14] Tan X, Jiang B. Simple algorithms for the planar 2-center problem[C]. International Computing and Combinatorics Conference. Springer, Cham, 2017: 481-491.
[15] Chan T M. More planar two-center algorithms[J]. Computational Geometry, 1999, 13(3): 189-198.
[16] Xu Y, Peng J, Xu Y, Zhu B. The discrete and mixed minimax 2-center problems[J]. Theoretical Computer Science, 2019, 774: 95-102.
[17] Bhattacharya B, Mozafari A, Shermer T C. An efficient algorithm for the proximity connected two center problem[C]. International Workshop on Combinatorial Algorithms. Springer, Cham, 2022: 199-213.
[18] Bajaj C. The algebraic degree of geometric optimization problems[J]. Discrete Computational Geometry, 1988, 3: 177-191.
[19] Ho J M, Lee D T, Chang C H, et al. Minimum diameter spanning trees and related problems[J]. SIAM Journal on Computing, 1991, 20(5): 987-997.
[20] Hassin R, Tamir A. On the minimum diameter spanning tree problem[J]. Information Processing Letters, 1995, 53(2): 109-111.
[21] Chan T M. Semi-online maintenance of geometric optima and measures[J]. SIAM Journal on Computing, 2003, 32(3): 700-716.

双会议服务器选址问题研究

Double Conference Servers Location Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	段倩倩, 彭春, 李金林. 基于鲁棒二阶随机占优的投资组合优化模型研究[J]. 运筹与管理, 2022, 31(8): 64-69.
[2]	李子慷, 刘林冬, 于成成. 范数下无容量限制设施选址逆问题的求解方法[J]. 运筹与管理, 2022, 31(7): 86-92.
[3]	姚金海. 基于ARIMA与信息粒化SVR组合的股指预测研究[J]. 运筹与管理, 2022, 31(5): 214-220.
[4]	彭大江, 叶春明, 赵灵玮. 改进的蝗虫优化算法在双目标应急物资中心选址问题中的应用[J]. 运筹与管理, 2022, 31(4): 14-20.
[5]	黄肖玲, 任宇婷, 张佳安, 王丹, 陈继红, 罗勋杰. 基于低碳环保因素的“前港后厂”钢铁产成品运输网络优化[J]. 运筹与管理, 2021, 30(8): 59-66.
[6]	王宗润, 何瑭瑭. 基于动态参照点的鲁棒投资组合模型及其拓展[J]. 运筹与管理, 2021, 30(6): 124-131.
[7]	唐颖峰, 陈世平. 分布式数据流处理系统管理中负载均衡问题建模与求解[J]. 运筹与管理, 2021, 30(4): 155-162.
[8]	徐弈, 陈莹. 最小最大二点集覆盖问题分析及改进算法设计[J]. 运筹与管理, 2020, 29(7): 33-40.
[9]	吴晨晨, 王丽, 徐春明, 徐大川. 鲁棒动态设施选址问题的近似算法[J]. 运筹与管理, 2020, 29(5): 61-66.
[10]	余谦,刘雅琴. 企业自主研发与合作创新的风险测度及组合优化[J]. 运筹与管理, 2019, 28(5): 77-83.
[11]	何永梅, 宁爱兵, 彭大江, 尚春剑, 张惠珍. 无容量限制设施选址问题的降阶回溯算法[J]. 运筹与管理, 2018, 27(9): 17-21.
[12]	陈国福, 陈小山, 张瑞. 基于引力搜索和粒子群混合优化算法的证券投资组合问题研究[J]. 运筹与管理, 2018, 27(9): 170-175.
[13]	张清叶, 高岩. 基于CVaR投资组合优化问题的光滑化方法[J]. 运筹与管理, 2017, 26(4): 158-164.
[14]	郑承利, 姚银红. 基于几种风险测度的多阶段组合优化研究[J]. 运筹与管理, 2017, 26(11): 35-41.
[15]	陆坚毅, 杨超, 揭婉晨. 考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法[J]. 运筹与管理, 2017, 26(1): 8-17.