2020/07/26 by Roughgarden, Tim
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2007.13234
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.