A polynomial-time DNA computing solution for the Bin-Packing Problem

被引：28
作者：
Alonso Sanches, Carlos Alberto
Soma, Nei Yoshihiro
机构：
[1] ITA, Computer Science Division
来源：
APPLIED MATHEMATICS AND COMPUTATION | 2009年 / 215卷 / 06期
基金：
巴西圣保罗研究基金会;
关键词：
DNA computing; Bin-Packing Problem; Parallel algorithm; ADLEMAN-LIPTON MODEL; MOLECULAR COMPUTATION; KNAPSACK-PROBLEM; ALGORITHMS;
D O I：
10.1016/j.amc.2009.07.051
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
It is suggested here an algorithm based on stickers for the DNA Computing model [S. Roweis, E. Winfree, R. Burgoyne, N. Chelyapov, M. Goodman, P. Rothemund, L. Adleman, A sticker-based model for DNA Computation, Journal of Computational Biology 5 (1998) 615-629] that solves the well known Bin-Packing Problem (BPP), that belongs to the class N P-Hard in the strong sense, in a time bounded by O(n(2)q), where n is the quantity of items and q the space requirements expressed in bits. To the best of the authors' knowledge, this is the first polynomial time algorithmic solution for the BPP in such a model. (C) 2009 Elsevier Inc. All rights reserved.
引用
收藏
页码：2055 / 2062
页数：8
相关论文
共 21 条
[1]   MOLECULAR COMPUTATION OF SOLUTIONS TO COMBINATORIAL PROBLEMS [J].
ADLEMAN, LM .
SCIENCE, 1994, 266 (5187) :1021-1024
[2]  
AMOS M, 1997, THESIS U WARWICK
[3]  
[Anonymous], 1979, COMPUTERS INTRACTABI
[4]  
Chang W.-L., 2002, IASTED INT C NETW PA, P455
[5]   Quantum algorithms for biomolecular solutions of the satisfiability problem on a quantum machine [J].
Chang, Weng-Long ;
Ren, Ting-Ting ;
Luo, Jun ;
Feng, Mang ;
Guo, Minyi ;
Lin, Kawuu Weicheng .
IEEE TRANSACTIONS ON NANOBIOSCIENCE, 2008, 7 (03) :215-222
[6]   Fast parallel DNA-based algorithms for molecular computation: The set-partition problem [J].
Chang, Weng-Long .
IEEE TRANSACTIONS ON NANOBIOSCIENCE, 2007, 6 (04) :346-353
[7]   Fast parallel molecular algorithms for DNA-based computation: Factoring integers [J].
Chang, WL ;
Guo, MY ;
Ho, MSH .
IEEE TRANSACTIONS ON NANOBIOSCIENCE, 2005, 4 (02) :149-163
[8]   Molecular solutions for the subset-sum problem on DNA-based supercomputing [J].
Chang, WL ;
Ho, MSH ;
Guo, M .
BIOSYSTEMS, 2004, 73 (02) :117-130
[9]   Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model [J].
Chang, WL ;
Guo, MY .
BIOSYSTEMS, 2003, 72 (03) :263-275
[10]   Molecular solution to the 0-1 knapsack problem based on DNA computing [J].
Darehmiraki, Majid ;
Nehi, Hasan Mishmast .
APPLIED MATHEMATICS AND COMPUTATION, 2007, 187 (02) :1033-1037
123