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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove the computational intractability of rotating and placing $n$ squaretiles into a $1 \times n$ array such that adjacent tiles are compatible--eitherequal edge colors, as in edge-matching puzzles, or matching tab/pocket shapes,as in jigsaw puzzles. Beyond basic NP-hardness, we prove that it is NP-hardeven to approximately maximize the number of placed tiles (allowing blanks),while satisfying the compatibility constraint between nonblank tiles, within afactor of 0.851. (On the other hand, there is an easy $1 \over2$-approximation.) This is the first (correct) proof of inapproximability foredge-matching and jigsaw puzzles. Along the way, we prove NP-hardness ofdistinguishing, for a directed graph on $n$ nodes, between having a Hamiltonianpath (length $n-1$) and having at most $0.284 (n-1)$ edges that form avertex-disjoint union of paths. We use this gap hardness and gap-preservingreductions to establish similar gap hardness for $1 \times n$ jigsaw andedge-matching puzzles.

Even $1 \times n$ Edge-Matching and Jigsaw Puzzles are Really Hard