论文标题

资源增强

Resource Augmentation

论文作者

Roughgarden, Tim

论文摘要

本章介绍了资源增强,其中将算法的性能与较少资源残障的最佳解决方案进行了比较。我们考虑三个案例研究:在线编码,缓存大小为资源;自私的路线,能力作为资源;和调度,以处理器速度作为资源。资源增强界限还意味着“竞争性宽松”,这表明算法的性能在大多数资源水平上几乎是最佳的。

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.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源