On the Hardness of Red-Blue Pebble Games
METADATA ONLY
Loading...
Author / Producer
Date
2020-07
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Red-blue pebble games model the computation cost of a two-level memory hierarchy. We present various hardness results in different red-blue pebbling variants, with a focus on the oneshot model. We first study the relationship between previously introduced red-blue pebble models (base, oneshot, nodel). We also analyze a new variant (compcost) to obtain a more realistic model of computation. We then prove that red-blue pebbling is NP-hard in all of these model variants. Furthermore, we show that in the oneshot model, a-approximation algorithm for <2 is only possible if the unique games conjecture is false. Finally, we show that greedy algorithms are not good candidates for approximation, since they can return significantly worse solutions than the optimum. © 2020 ACM.
Permanent link
Publication status
published
External links
Editor
Book title
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
Journal / series
Volume
Pages / Article No.
419 - 429
Publisher
Association for Computing Machinery
Event
32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020) (virtual)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Red-blue pebble game; Time-memory trade off
Organisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger
Notes
Due to the Corona virus (COVID-19) the conference was conducted virtually.