Approximability of Edge Matching Puzzles

摘要

This paper deals with the (in)approximability of Edge Matching Puzzles. The interest in EdgeMatching Puzzles has been raised in the last few years with the release of the Eternity II? puzzle, with a $2 million prize for the first submitted correct solution. It is known [1] that it is NP-hard to obtain an exact solution to Edge Matching Puzzles. We extend on that result by showing an approximation-preserving reduction from Max-3DM-B and thus proving that Edge Matching Puzzles do not admit polynomial-time approximation schemes unless P=NP. We then show that the problem is APX-complete, and study the difficulty of finding an approximate solution for several other optimisation variants of the problem.