Approximability of edge matching puzzles

Antonios Antoniadis; Andrzej Lingas

doi:10.1007/978-3-642-11266-9

Approximability of edge matching puzzles

Antonios Antoniadis
, Andrzej Lingas

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	SOFSEM 2010: Theory and Practice of Computer Science
Subtitle of host publication	36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010. Proceedings
Editors	Jan van Leeuwen, Anca Muscholl, David Peleg, Jaroslav Pokorný, Bernhard Rumpe
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	153-164
ISBN (Electronic)	978-3-642-11266-9
ISBN (Print)	978-3-642-11265-2
DOIs	https://doi.org/10.1007/978-3-642-11266-9
Publication status	Published - 2010
Externally published	Yes
Event	36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010 - Špindleruv Mlýn, Czech Republic Duration: 23 Jan 2010 → 29 Jan 2010 Conference number: 36

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5901
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010
Abbreviated title	SOFSEM 2010
Country/Territory	Czech Republic
City	Špindleruv Mlýn
Period	23/01/10 → 29/01/10

Access to Document

10.1007/978-3-642-11266-9

Cite this

Antoniadis, A., & Lingas, A. (2010). Approximability of edge matching puzzles. In J. van Leeuwen, A. Muscholl, D. Peleg, J. Pokorný, & B. Rumpe (Eds.), SOFSEM 2010: Theory and Practice of Computer Science: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010. Proceedings (pp. 153-164). (Lecture Notes in Computer Science; Vol. 5901). Springer. https://doi.org/10.1007/978-3-642-11266-9

Antoniadis, Antonios ; Lingas, Andrzej. / Approximability of edge matching puzzles. SOFSEM 2010: Theory and Practice of Computer Science: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010. Proceedings. editor / Jan van Leeuwen ; Anca Muscholl ; David Peleg ; Jaroslav Pokorný ; Bernhard Rumpe. Berlin, Heidelberg : Springer, 2010. pp. 153-164 (Lecture Notes in Computer Science).

@inproceedings{a7b326f88dba49b99da02f6c41c0b8ae,

title = "Approximability of edge matching puzzles",

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. ",

author = "Antonios Antoniadis and Andrzej Lingas",

year = "2010",

doi = "10.1007/978-3-642-11266-9",

language = "English",

isbn = "978-3-642-11265-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "153--164",

editor = "\{van Leeuwen\}, Jan and Anca Muscholl and David Peleg and Jaroslav Pokorn{\'y} and Bernhard Rumpe",

booktitle = "SOFSEM 2010: Theory and Practice of Computer Science",

address = "Germany",

note = "36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, SOFSEM 2010 ; Conference date: 23-01-2010 Through 29-01-2010",

}

Antoniadis, A & Lingas, A 2010, Approximability of edge matching puzzles. in J van Leeuwen, A Muscholl, D Peleg, J Pokorný & B Rumpe (eds), SOFSEM 2010: Theory and Practice of Computer Science: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010. Proceedings. Lecture Notes in Computer Science, vol. 5901, Springer, Berlin, Heidelberg, pp. 153-164, 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, Špindleruv Mlýn, Czech Republic, 23/01/10. https://doi.org/10.1007/978-3-642-11266-9

Approximability of edge matching puzzles. / Antoniadis, Antonios; Lingas, Andrzej.
SOFSEM 2010: Theory and Practice of Computer Science: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010. Proceedings. ed. / Jan van Leeuwen; Anca Muscholl; David Peleg; Jaroslav Pokorný; Bernhard Rumpe. Berlin, Heidelberg: Springer, 2010. p. 153-164 (Lecture Notes in Computer Science; Vol. 5901).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximability of edge matching puzzles

AU - Antoniadis, Antonios

AU - Lingas, Andrzej

N1 - Conference code: 36

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-11266-9

DO - 10.1007/978-3-642-11266-9

M3 - Conference contribution

SN - 978-3-642-11265-2

T3 - Lecture Notes in Computer Science

SP - 153

EP - 164

BT - SOFSEM 2010: Theory and Practice of Computer Science

A2 - van Leeuwen, Jan

A2 - Muscholl, Anca

A2 - Peleg, David

A2 - Pokorný, Jaroslav

A2 - Rumpe, Bernhard

PB - Springer

CY - Berlin, Heidelberg

T2 - 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010

Y2 - 23 January 2010 through 29 January 2010

ER -

Antoniadis A, Lingas A. Approximability of edge matching puzzles. In van Leeuwen J, Muscholl A, Peleg D, Pokorný J, Rumpe B, editors, SOFSEM 2010: Theory and Practice of Computer Science: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010. Proceedings. Berlin, Heidelberg: Springer. 2010. p. 153-164. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-11266-9

Approximability of edge matching puzzles

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this