Adleman, Leonard and Cheng, Qi and Goel, Ashish and Huang, Ming-Deh and Kempe, David and Moisset de Espanés, Pablo and Rothemund, Paul Wilhelm Karl
(2002)
*Combinatorial optimization problems in self-assembly.*
In:
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, Montreal, Quebec, Canada, May 19-21, 2002 (STOC '02).
ACM Press
, New York, NY, pp. 23-32.
ISBN 1-58113-495-9.
https://resolver.caltech.edu/CaltechAUTHORS:ADLstoc02

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:ADLstoc02

## Abstract

Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the Tile Assembly Model of self-assembly proposed by Rothemund and Winfree [18]. The first is the Minimum Tile Set Problem, where the goal is to find the smallest tile system that uniquely produces a given shape. The second is the Tile Concentrations Problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. The first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape.Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the Tile Assembly Model of self-assembly proposed by Rothemund and Winfree [18]. The first is the Minimum Tile Set Problem, where the goal is to find the smallest tile system that uniquely produces a given shape. The second is the Tile Concentrations Problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. The first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape. We prove that the first problem is NP-complete in general, and polynomial time solvable on trees and squares. In order to prove that the problem is in NP, we present a polynomial time algorithm to verify whether a given tile system uniquely produces a given shape. This algorithm is analogous to a program verifier for traditional computational systems, and may well be of independent interest. For the second problem, we present a polynomial time $O(\log n)$-approximation algorithm that works for a large class of tile systems that we call partial order systems.

Item Type: | Book Section | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| ||||||||||||||

ORCID: |
| ||||||||||||||

Additional Information: | Copyright © 2002 ACM, Inc. Leonard Adleman’s research was supported in part by grants from NASA/JPL, NSF, ONR, and DARPA. Qi Cheng’s research was supported in part by NSF Grant CCR-9820778. Ashish Goel’s research was supported in part by a grant from NASA. Ming-deh Huang’s research was supported in part by a grant from NASA and by NSF Grant CCR-9820778. David Kempe’s research was supported by an Intel Fellowship. Pablo Moisset de Espanés’s research was supported in part by a grant from NASA. Paul Rothemund’s research was supported by a Beckman Senior Research Fellowship. We would like to thank Matt Cook, Lila Kari, and Erik Winfree for useful discussions about self-assembly in general, and the topics studied in this paper in particular. | ||||||||||||||

Funders: |
| ||||||||||||||

Subject Keywords: | Combinatorial algorithms, Constrained optimization, Spline and piecewise polynomial approximation | ||||||||||||||

Record Number: | CaltechAUTHORS:ADLstoc02 | ||||||||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:ADLstoc02 | ||||||||||||||

Alternative URL: | http://doi.acm.org/10.1145/509907.509913 | ||||||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||

ID Code: | 3141 | ||||||||||||||

Collection: | CaltechAUTHORS | ||||||||||||||

Deposited By: | Archive Administrator | ||||||||||||||

Deposited On: | 16 May 2006 | ||||||||||||||

Last Modified: | 02 Oct 2019 23:00 |

Repository Staff Only: item control page