论文标题
资源增强
Resource Augmentation
论文作者
论文摘要
本章介绍了资源增强，其中将算法的性能与较少资源残障的最佳解决方案进行了比较。我们考虑三个案例研究：在线编码，缓存大小为资源；自私的路线，能力作为资源；和调度，以处理器速度作为资源。资源增强界限还意味着“竞争性宽松”，这表明算法的性能在大多数资源水平上几乎是最佳的。
This chapter introduces resource augmentation, in which the performance of an algorithm is compared to the best-possible solution that is handicapped by less resources. We consider three case studies: online paging, with cache size as the resource; selfish routing, with capacity as the resource; and scheduling, with processor speed as the resource. Resource augmentation bounds also imply "loosely competitive" bounds, which show that an algorithm's performance is near-optimal for most resource levels.
