| 最小最大二点集覆盖问题分析及改进算法设计 |
| |
| 引用本文： | 徐弈,陈莹.最小最大二点集覆盖问题分析及改进算法设计[J].运筹与管理,2020,29(7):33-40. |
| |
| 作者姓名： | 徐弈 陈莹 |
| |
| 作者单位： | 1.西安理工大学 经济与管理学院,陕西 西安 710054;2.西安交通大学 管理学院,陕西 西安 710049 |
| |
| 基金项目： | 陕西省自然科学基础研究计划(青年人才项目)(2020JQ-654) ;西安理工大学校博士启动金(105-451119001) |
| |
| 摘 要： | 本文考虑二中心问题的扩展问题-最小最大二点集覆盖问题。给定两个平面点集P1和P2,分别包含m和n个点,求两个圆分别覆盖P1和P2,并且要求两圆半径与两圆圆心距三者中的最大值最小。本文主要贡献在于分析半径变化过程中两个点集中心包之间最近距离的变化关系,其中中心包是点集所具有的一个特殊几何结构,所得到的结果改进了Huang等人之前给出的结果,并且通过该结果设计相应算法,所得到的算法复杂性是目前最好的。
|
| 关 键 词： | 二中心问题 最远点Voronoi图 中心包 选址问题 |
| 收稿时间： | 2018-12-10 |
The Minimax 2-point Sets Covering Problem and Improved Algorithm |
| |
| XU Yi,CHEN Ying.The Minimax 2-point Sets Covering Problem and Improved Algorithm[J].Operations Research and Management Science,2020,29(7):33-40. |
| |
| Authors: | XU Yi CHEN Ying |
| |
| Affiliation: | 1. School of Economics and Management, Xi'an University of Technology, Xi'an710054, China;2. School of Management, Xi'an Jiaotong University, Xi'an 710049, China |
| |
| Abstract: | For a variation of two center problem, we consider the minimax 2-point sets covering problem. This problem considers finding two disks covering two point sets respectively such that the maximum among the two radii and the distance between two centers is minimized. According to the relationship between a center hull and the farthest point Voronoi diagram, when the radius is increasing from 0, we propose the minimum distance between two center hulls. We improve the previous result and give an improved algorithm which is the best known algorithm so far. |
| |
| Keywords: | 2-center problem farthest point Voronoi diagram center hull facility location problem |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
|
点击此处可从《运筹与管理》下载全文 |
|
