A molecular solution for minimum vertex cover problem in tile assembly model

Self-assembly is a generalization of the crystal growth, which has been proposed as a mechanism for the bottom-up fabrication of autonomous DNA computation. In the same context, tile assembly model is a highly distributed parallel model of natural self-assembly. In this paper, we propose a tile assembly system to tackle a well-known NP-complete problem known as Minimum Vertex Cover problem. The proposed algorithm requires Θ(n×m) types of tiles, and each parallel assembly executes in a linear time, where n is the number of vertices and m is the number of edges. Furthermore, the experimental results proved the simplicity and the efficiency of the proposed algorithm to solve the Minimum Vertex Cover, and reduce the overall complexity to find the solution.     

Path finding in the tile assembly model

Swarm robotics, active self-assembly, and amorphous computing are fields that focus on designing systems of large numbers of small, simple components that can cooperate to complete complex tasks. Many of these systems are inspired by biological systems, and all attempt to use the simplest components and environments possible, while still being capable of achieving their goals. The canonical problems for such biologically-inspired systems are shape assembly and path finding. In this paper, we demonstrate path finding in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. As in related work, our systems function in the presence of obstacles and can be made fault-tolerant. The path-finding systems use Θ(1)$\Theta \left(1\right)$ distinct components and find minimal-length paths in time linear in the length of the path.     

Efficient 3-SAT algorithms in the tile assembly model

Self-assembly is a powerful process found in nature that guides simple objects assembling, on their own, into complex structures. Self-assembly is of interest to computer scientists because self-assembling systems can compute functions, assemble shapes, and guide distributed robotics systems. The tile assembly model is a formal mathematical model of self-assembly that allows the study of time and space complexities of self-assembling systems that lie at the heart of several molecular computer implementations and distributed computational software systems. These implementations and systems require efficient tile systems with small tilesets and fast execution times. The state of the art, however, requires vastly complex tile systems with large tilesets to implement fast algorithms. In this paper, I present ${\mathbb{S}}_{FS},$ a tile system that decides 3-SAT by creating $O^{\star}(1.8393^n)$ nondeterministic assemblies in parallel, improving on the previous best known solution that requires $\Uptheta(2^n)$ such assemblies. This solution directly improves the feasibility of building molecular 3-SAT solvers and efficiency of distributed software. I formally prove the correctness of the system, the number of required parallel assemblies, that the size of the system??s tileset is $147 = \Uptheta(1),$ and that the assembly time is nondeterministic linear in the size of the input.     

Nondeterministic polynomial time factoring in the tile assembly model

Formalized study of self-assembly has led to the definition of the tile assembly model, Previously I presented ways to compute arithmetic functions, such as addition and multiplication, in the tile assembly model: a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Here, I present tile assembly model systems that factor numbers nondeterministically using Θ(1)$\Theta \left(1\right)$ distinct components. The computation takes advantage of nondeterminism, but theoretically, each of the nondeterministic paths is executed in parallel, yielding the solution in time linear in the size of the input, with high probability. I describe mechanisms for finding the successful solutions among the many parallel executions and explore bounds on the probability of such a nondeterministic system succeeding and prove that the probability can be made arbitrarily close to 1.     

Arithmetic computation in the tile assembly model: Addition and multiplication

Formalized study of self-assembly has led to the definition of the tile assembly model [Erik Winfree, Algorithmic self-assembly of DNA, Ph.D. Thesis, Caltech, Pasadena, CA, June 1998; Paul Rothemund, Erik Winfree, The program-size complexity of self-assembled squares, in: ACM Symposium on Theory of Computing, STOC02, Montreal, Quebec, Canada, 2001, pp. 459–468]. Research has identified two issues at the heart of self-assembling systems: the number of steps it takes for an assembly to complete, assuming maximum parallelism, and the minimal number of tiles necessary to assemble a shape. In this paper, I define the notion of a tile assembly system that computes a function, and tackle these issues for systems that compute the sum and product of two numbers. I demonstrate constructions of such systems with optimal Θ(1)$\Theta \left(1\right)$ distinct tile types and prove the assembly time is linear in the size of the input.     

The effect of malformed tiles on tile assemblies within the kinetic tile assembly model

Many different constructions of proofreading tile sets have been proposed in the literature to reduce the effect of deviations from ideal behaviour of the dynamics of the molecular tile self-assembly process. In this paper, we consider the effect on the tile assembly process of a different kind of non-ideality, namely, imperfections in the tiles themselves. We assume a scenario in which some small proportion of the tiles in a tile set are “malformed”. We study, through simulations, the effect of such malformed tiles on the self-assembly process within the kinetic Tile Assembly Model (kTAM). Our simulation results show that some tile set constructions show greater error-resilience in the presence of malformed tiles than others. For example, the 2- and 3-way overlay compact proofreading tile sets of Reif et al. (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) are able to handle malformed tiles quite well. On the other hand, the snaked proofreading tile set of Chen and Goel (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) fails to form even moderately sized tile assemblies when malformed tiles are present. We show how the Chen–Goel construction may be modified to yield new snaked proofreading tile sets that are resilient not only to errors intrinsic to the assembly process, but also to errors caused by malformed tiles.     

An exact algorithm for minimum distortion embedding

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5^n+o(n). This is the first algorithm breaking the trivial n!-barrier.     

Genetic algorithms for sequencing problems in mixed model assembly lines

Mixed model assembly lines are a type of production line where a variety of product models similar in product characteristics are assembled. The effective utilisation of these lines requires that a schedule for assembling the different products be determined. In this paper, the performance of genetic algorithms for sequencing problems in mixed model assembly lines is investigated. The problem first considered is a comparison between a existing heuristic and the proposed genetic algorithm to get the constant usage of every part used by the line considering variation at multi levels (Number of levels fixed as four. level 1—product, level 2—subassembly, level 3—component, level 4—raw-materials) for various test-bed problems. The algorithms proposed by Miltenburg and Sinnamon hereafter referred to as MS 1992 [IIE Trans. 24 (1992) 121] and the proposed genetic algorithm (GA) applied to mixed model assembly line are compared. Results of evaluation indicate that the GA performs better over MS1992 on 25 of the 40 problems investigated.

The other problem solved is a multiple objective sequencing problem in mixed model assembly lines. Three practically important objectives are minimizing total utility work keeping a constant rate of part-usage, minimizing the variability in parts usage and minimizing total setup cost. In this paper, the performance of the selection mechanisms, the Pareto stratum-niche cubicle and the selection based on scalar fitness function value are compared with respect to the objective of minimising variation in part-usage, minimising total utility work and minimising the setup cost. Results of evaluation indicate that the genetic algorithm that uses the Pareto stratum-niche cubicle performs better than the genetic algorithm with the other selection mechanisms.     

Complexities of efficient solutions of rectilinear polygon cover problems

The rectilinear polygon cover problem is one in which a certain class of features of a rectilinear polygon ofn vertices has to be covered with the minimum number of rectangles included in the polygon. In particular, we consider covering the entire interior, the boundary, and the set of corners of the polygon. These problems have important applications in storing images and in the manufacture of integrated circuits. Unfortunately, most of these problems are known to be NP-complete. Hence it is necessary to develop efficient heuristics for these problems or to show that the design of efficient heuristics is impossible. In this paper we show:

New exact solutions for a chiral cosmological model in 5D EGB gravity

We consider a chiral cosmological model in the framework of Einstein–Gauss–Bonnet cosmology. Using a decomposition of the latter equations in such a way that the first chiral field is responsible for the Einstein part of the model while the second field together with the kinetic interaction is connected with the Gauss–Bonnet part of the theory, we find new exact solutions for the 2-component chiral cosmological model with and without a kinetic interaction between the fields.     

Parallel and serial heuristics for the minimum set cover problem

We present a theoretical analysis and an experimental evaluation of four serial heuristics and four parallel heuristics for the minimum set cover problem. The serial heuristics trade off run time with the quality of the solution. The parallel heuristics are derived from one of the serial heuristics. These heuristics show considerable speedup when the number of processors is increased. The quality of the solution computed by the heuristics does not degrade with an increase in the number of processors.Research of both authors was supported by NSF Grant No. MIP-8807540.     

A parallel algorithm for approximating the minimum cycle cover

We address the problem of approximating aminimum cycle cover in parallel. We give the first efficient parallel algorithm for finding an approximation to aminimum cycle cover. Our algorithm finds a cycle cover whose size is within a factor of 0(1 +n logn/(m + n) of the minimum-sized cover usingO(log² n) time on (m + n)/logn processors.Research supported by ONR Grant N00014-88-K-0243 and DARPA Grant N00039-88-C0113 at Harvard University.Research supported by a graduate fellowship from GE. Additional support provided by Air Force Contract AFOSR-86-0078, and by an NSF PYI awarded to David Shmoys, with matching funds from IBM, Sun Microsystems, and UPS.     

Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation–linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time.     

Exact solutions to some minimum time problems with inequality state constraints

A heuristic method is developed for generating exact solutions to certain minimum time problems, with inequality state and control constraints. The control equation is linear and autonomous, with scalar-valued control. The state constraints are also linear inequalities. Assuming knowledge of a finite sequence, in which state and/or control constraints become active along an optimal path, the maximum principle is reduced to a set of equations and inequalities in a finite number of unknowns. A solution to the equations and inequalities determines both the solution path and a proof of its optimality. Certain types of constraint sequences lead to overdetermined equation systems, and this fact is interpreted in terms of the qualitative behavior of solutions to these problems. Two path-planning problems are solved, as illustrations of the solution technique.     

最小顶点覆盖问题的竞争决策算法

竞争决策算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就优化、决策左右结果的特性来达到优化目的的新型寻优算法。采用竞争决策算法原理,利用竞争决策算法的通用模型,求解图的最小顶点覆盖问题。