限制图上的局内出租车调度与竞争算法

摘要：

经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解) ,其最优性在条件发生变化时就会失去.局内问题与竞争算法则是针对特定的优化问题来研究这样的方法,它在变化因素的每一个特例中都能给出一个方案,使得这一方案所得到的解离最优方案给出的解总在一定的比例之内.本文应用复位策略给出限制图上局内k出租车调度问题竞争比为1+(n-k)λ的竞争算法.

关键词：局内问题、竞争算法、竞争比

所属期刊栏目：14

分类号：TB114.1(工程基础科学)

资助基金：国家高技术研究发展计划863计划19731001;西安交通大学校科研和教改项目

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：361-365