Approximability of edge matching puzzles

Antonios Antoniadis, Andrzej Lingas

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract

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 TM puzzle, with a $2 million prize for the first submitted correct solution. It is known [1] 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.

Original languageEnglish
Title of host publicationSOFSEM 2010: Theory and Practice of Computer Science
Subtitle of host publication36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010. Proceedings
EditorsJan van Leeuwen, Anca Muscholl, David Peleg, Jaroslav Pokorný, Bernhard Rumpe
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages153-164
ISBN (Electronic)978-3-642-11266-9
ISBN (Print)978-3-642-11265-2
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010 - Špindleruv Mlýn, Czech Republic
Duration: 23 Jan 201029 Jan 2010
Conference number: 36

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5901
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010
Abbreviated titleSOFSEM 2010
CountryCzech Republic
CityŠpindleruv Mlýn
Period23/01/1029/01/10

Fingerprint

Dive into the research topics of 'Approximability of edge matching puzzles'. Together they form a unique fingerprint.

Cite this