| 占线中心选址问题竞争比的下界 |
| |
| 引用本文： | 代文强,徐寅峰,李毅学.占线中心选址问题竞争比的下界[J].系统工程,2006,24(8):98-101. |
| |
| 作者姓名： | 代文强 徐寅峰 李毅学 |
| |
| 作者单位： | 1. 西安交通大学,管理学院,陕西,西安,710049
2. 西安交通大学,管理学院,陕西,西安,710049;西安交通大学,机械制造系统工程国家重点实验室,陕西,西安,710049 |
| |
| 基金项目： | 国家自然科学基金;国家自然科学基金;高等学校博士学科点专项科研项目 |
| |
| 摘 要： | 对占线中心选址问题的竞争比进行了研究。对度量空间占线中心选址问题，本文证明该问题的下界是2-（n-√n^2-3n＋3/n-1），其中n为空间点的个数，该结果要优于已有的结果2-（2/n-1）.对一般空间上的占线中心选址问题，本文证明了竞争比的下界是（（n-2）△＋√（n-2）^2△^2＋4（n-2））/2（n-1）,其中△是所给空间最大的相对距离，并证明一般空间上的占线中心选址问题不存在常数竞争算法。
|
| 关 键 词： | 运筹学 选址问题 占线中心 竞争比 |
| 文章编号： | 1001-4098（2006）08-0098-04 |
| 收稿时间： | 2006-07-03 |
| 修稿时间： | 2006-07-03 |
Lower Bound for the Competitive Ratio of Online Median Problem |
| |
| DAI Wen-qiang,XU Yin-feng,LI Yi-xue.Lower Bound for the Competitive Ratio of Online Median Problem[J].Systems Engineering,2006,24(8):98-101. |
| |
| Authors: | DAI Wen-qiang XU Yin-feng LI Yi-xue |
| |
| Abstract: | |
| |
| Keywords: | Operational Research Facility Location Problem Online Median Competitive Ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
