The Application of DNA Self-Assembly Model for Bin Packing Problem

The Application of DNA Self-Assembly Model for Bin Packing Problem

Yanfeng Wang (Zhengzhou University of Light Industry, China), Xuewen Bai (Zhengzhou University of Light Industry, China), Donghui Wei (Zhengzhou University of Light Industry, China), Weili Lu (Zhengzhou University of Light Industry, China) and Guangzhao Cui (Zhengzhou University of Light Industry, China)
Copyright: © 2012 |Pages: 15
DOI: 10.4018/jncr.2012010101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Bin Packing Problem (BPP) is a classical combinatorial optimization problem of graph theory, which has been proved to be NP-complete, and has high computational complexity. DNA self-assembly, a formal model of crystal growth, has been proposed as a mechanism for the bottom-up fabrication of autonomous DNA computing. In this paper, the authors propose a DNA self-assembly model for solving the BPP, this model consists of two units: grouping based on binary method and subtraction system. The great advantage of the model is that the number of DNA tile types used in the model is constant and it can solve any BPP within linear time. This work demonstrates the ability of DNA tiles to solve other NP-complete problems in the future.
Article Preview

Introduction

The BPP can be simply described as follows: put a certain number of items into some boxes with the same volume, make the volume sum of the items in each box not exceed the volume of the box, and finally ensure that the number of the boxes used in the process is the least. It is a typical combinatorial optimization problem, and involved in many fields, especially in the field of computer science and industry, it has extensive application background, such as multi-processor scheduling, memory management, resource allocation, transportation plan and so on (Johnson, 1974), so the research of bin packing problem has wide application value.

Up to now, researchers have proposed many solutions and approximation algorithms to solve the BPP, such as the grouping genetic algorithm (Falkenauer, 1996), hybrid genetic algorithm (Reeves, 1996), Ant colony optimization(Levine & Ducatelle, 2004), the next adaptation, the first adaptation, the descending next fit, the best adaptation and so on (Coffman, Garey, & Johnson, 1996), whereas the results have a great relationship with the volume of the items when using these approximate algorithm to solve the problem with complex constraints.

However, the DNA self-assembly can solve the above problem in theory. DNA self-assembly is one of the most important applications of DNA computation, and the process is cost effective, versatile, facile, and the process occurs towards the system’s thermodynamic minima, resulting in stable and robust structures (Lehn, 1993). The relation of DNA computation with self-assembling structures was developed in the mid-1990s, largely through the theoretical and experimental work of Adleman (1994), Winfree, Eng, and Rozenberg (2001)Winfree (1998), Seeman (1998), Reif (2002), and Rozenberg and Spaink (2003). Because of its massive parallel computing function and large amounts of information storage ability, it has gradually become a mainstream method to solve the basic arithmetic problems and NP-Complete problems. For example, Arithmetic computation in the tile assembly model: Addition and multiplication (Brun, 2007), Arithmetic computation using self-assembly of DNA tiles: subtraction and division (Brun, 2008), Solving satisðability in the tile assembly model with a constant-size tileset (Zhang, Wang, Chen, Xu, & Cui, 2009), DNA self-assembly for the minimum vertex cover problem (Wang, Hu, Zhang, & Cui, 2011), DNA 3D self-assembly algorithmic model to solve the maximum clique problem (Ma, Li, & Dong, 2011), 3D DNA self-assembly model for graph vertex coloring (Lin, Xu, & Zhang, 2010), Application of DNA computing by self-assembly on 0-1 knapsack problem (Cui, Li, Zhang, Wang, Qi, Li, & Li, 2009), Application of DNA self-assembly on maximum clique problem (Cui, Li, Li, Zhang, & Li, 2009), DNA tile assembly model for 0-1 knapsack problem (Wang, Lu, Zhang, & Cui, 2010) and so on.

In this paper, we propose a DNA self-assembly model with a subtraction system for solving the Bin Packing problem. The rest of the paper is organized as follows: First we describe the basic knowledge and the mechanism of DNA self-assembly; we give the definition of the Bin Packing problem; we then show the DNA self-assembly model for solving the Bin Packing problem; finally, we give a conclusion.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 6: 2 Issues (2017): 1 Released, 1 Forthcoming
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing