Algorithm Engineering and Experiments
Lecture Notes in Computer Science, 2002, Volume 2409/2002, 73-82, DOI: 10.1007/3-540-45643-0_5

Evaluating the Local Ratio Algorithm for Dynamic Storage Allocation

Kirk Pruhs and Eric Wiewiora

View Related Documents

Abstract

We empirically compare the local ratio algorithm for the profit maximization version of the dynamic storage allocation problem against various greedy algorithms. Our main conclusion is that, at least on our input distributions, the local ratio algorithms performed worse on average than the more naive greedy algorithms.
Supported in part by NSF grants CCR-9734927, CCR-0098752, ANIR-0123705, and by a grant from the US Air Force.

Fulltext Preview

Image of the first page of the fulltext document