论文标题
关于红蓝色卵石游戏的硬度
On the Hardness of Red-Blue Pebble Games
论文作者
论文摘要
Red-Blue Pebble Games建模了两级内存层次结构的计算成本。我们介绍了各种硬度结果，以不同的红蓝色卵石变体，重点是Onehot模型。我们首先研究了先前引入的红蓝色卵石模型（基础，Oneshot，Nodel）之间的关系。我们还分析了一个新的变体（COMPCOST），以获得更现实的计算模型。然后，我们证明在所有这些模型变体中，红蓝色卵石都是NP-固定的。此外，我们表明，在Oneshot模型中，仅当唯一游戏猜想是错误的时候，只有$Δ<2 $的$δ$ - approximation算法才有可能。最后，我们表明，贪婪的算法不是近似的好候选者，因为它们的解决方案明显差于最佳。
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.
