English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Red-blue pebble games model the computation cost of a two-level memoryhierarchy. We present various hardness results in different red-blue pebblingvariants, with a focus on the oneshot model. We first study the relationshipbetween previously introduced red-blue pebble models (base, oneshot, nodel). Wealso analyze a new variant (compcost) to obtain a more realistic model ofcomputation. We then prove that red-blue pebbling is NP-hard in all of thesemodel variants. Furthermore, we show that in the oneshot model, a$\delta$-approximation algorithm for $\delta<2$ is only possible if the uniquegames conjecture is false. Finally, we show that greedy algorithms are not goodcandidates for approximation, since they can return significantly worsesolutions than the optimum.

On the Hardness of Red-Blue Pebble Games