CaltechAUTHORS
  A Caltech Library Service

Combinatorial optimization problems in self-assembly

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:
URLURL TypeDescription
http://doi.acm.org/10.1145/509907.509913PublisherArticle
ORCID:
AuthorORCID
Rothemund, Paul Wilhelm Karl0000-0002-1653-3202
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:
Funding AgencyGrant Number
NASA/JPLUNSPECIFIED
NSFCCR-9820778
Office of Naval Research (ONR)UNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
IntelUNSPECIFIED
Arnold and Mabel Beckman FoundationUNSPECIFIED
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