Parallel prefetching and caching is NP-hard
Christoph Ambühl, Weber, Brigitta · Repository for Publications and Research Data (ETH Zurich) · 2003
In this paper we study integrated prefetching and caching in parallel disk systems. This topic has gained a lot of interest in the last years which manifests itself in numerous recent approximation algorithms. This paper provides the first negative result in this area. Specifically we show that computing an optimum prefetching/caching schedule for a parallel disk system is NP-hard, which settles an open problem posed in many papers.