Speaker
Dr
Eugen Czeizler
(Aalto University)
Description
We consider the problem of finding, for a given 2D
pattern of coloured tiles, a minimal set of tiles
assembling this pattern (in the abstract Tile Assembly
Model of Winfree (1998)). This Patterned self-Assembly
Tile set Synthesis (PATS) problem was first introduced by
Ma and Lombardi (2008), and subsequently studied by
Goos and Orponen (2010), who presented an
exhaustive partition-search branch-and-bound
algorithm. Later we shifted to the problem of finding
small (maybe not minimal) and reliable solutions, in a
reasonable time interval, Lempiainen et al. (2011). We
modified the basic partition search framework by using a
heuristic to optimize the order in which the algorithm
traverses its search space. The new algorithm was able
to shorten considerably the time needed for finding small
(minimal, or close to minimal) tile sets. In a recent
breakthrough, we showed that the PATS problem is NP
hard by providing a reduction from the 3SAT problem.
Thus, local search algorithms for PATS remain the default
solution for finding acceptable solutions in a reasonable
time interval.
Primary author
Dr
Eugen Czeizler
(Aalto University)
