Narrow Results

The purpose of this paper is to suggest a new parallel algorithm for the knapsack problem. The design of the proposed parallel algorithm is based on a shared memory SIMD machine with a heap tree data structure. It can solve a general n-component knapsack problem in time O(2^n/2) with memory-processor tradeoff M²P = O(2^n/2). The proposed technique can have better performance in terms of cost as the number of processors needed can be offset by increasing memory space. The performance is compared with those of other algorithms to demonstrate its superiority. We believe that the proposed algorithm is pragmatically feasible at the moment when multiprocessor systems are gradually becoming popular.

The knapsack problem is known to be a typical NP-complete problem, which has 2ⁿ possible solutions to search over. Thus a task for solving the knapsack problem can be accomplished in 2ⁿ trials if an exhaustive search is applied. In the past decade, much effort has been devoted in order to reduce the computation time of this problem instead of exhaustive search. In 1984, Karnin proposed a brilliant parallel algorithm, which needs O(2^n/6) processors to solve the knapsack problem in O(2^n/2) time; that is, the cost of Karnin's parallel algorithm is O(2^2n/3). In this paper, we propose a fast search technique to improve Karnin's parallel algorithm by reducing the search time complexity of Karnin's parallel algorithm to be O(2^n/3) under the same O(2^n/6) processors available. Thus, the cost of the proposed parallel algorithm is O(2^n/2). Furthermore, we extend this search technique to the case that the number of available processors is P = O(2^x), where x ≥ 1. From the analytical results, we see that our search technique is indeed superior to the previously proposed methods. We do believe our proposed parallel algorithm is pragmatically feasible at the moment when multiprocessor systems become more and more popular.

In this paper, based on maximum neural network, we propose a new parallel algorithm that can help the maximum neural network escape from local minima by including a transient chaotic neurodynamics for bipartite subgraph problem. The goal of the bipartite subgraph problem, which is an NP–complete problem, is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. Lee et al. presented a parallel algorithm using the maximum neural model (winner-take-all neuron model) for this NP–complete problem. The maximum neural model always guarantees a valid solution and greatly reduces the search space without a burden on the parameter-tuning. However, the model has a tendency to converge to a local minimum easily because it is based on the steepest descent method. By adding a negative self-feedback to the maximum neural network, we proposed a new parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm is then fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the maximum neural network and the chaotic neurodynamics. A large number of instances have been simulated to verify the proposed algorithm. The simulation results show that our algorithm finds the optimum or near-optimum solution for the bipartite subgraph problem superior to that of the best existing parallel algorithms.

The classic spiking neural P (SN P) systems abstract the real biological neural network into a simple structure based on graphs, where neurons can only communicate on the plane. This study proposes the hypergraph-based numerical spiking neural membrane (HNSNM) systems with novel repartition protocols. Through the introduction of hypergraphs, the HNSNM systems can characterize the high-order relationships among neurons and extend the traditional neuron structure to high-dimensional nonlinear spaces. The HNSNM systems also abstract two biological mechanisms of synapse creation and pruning, and use plasticity rules with repartition protocols to achieve planar, hierarchical and spatial communications among neurons in hypergraph neuron structures. Through imitating register machines, the Turing universality of the HNSNM systems is proved by using them as number generating and accepting devices. A universal HNSNM system consisting of 41 neurons is constructed to compute arbitrary functions. By solving NP-complete problems using the subset sum problem as an example, the computational efficiency and effectiveness of HNSNM systems are verified.

In this paper, we propose a parallel algorithm for the traffic control problem (an NP-complete problem) on crossbar switch networks. This problem is to find a set of conflict-free paths such that the maximum number of message packets can be transmitted over the network. The problem can be represented by an energy function. Then by applying our parallel algorithm, the state of the energy function is iteratively updated toward a stable state. When the energy function reaches a stable state, the state represents a solution of the problem. The empirical results show that the throughputs of the proposed algorithm are much better than the linear algorithm. We have shown that the time complexity of a parallel algorithm is O(n) by using n² processors. Furthermore, since the traffic control problem can be reduced to the traveling salesman problem, the proposed algorithm can be further applied to some other NP-complete problems.

The maximal matching problem (MMP) is to find maximal edge subsets in a given undirected graph, that no pair of edges are adjacent in the subsets. It is a vitally important NP-complete problem in graph theory and applied mathematics, having numerous real life applications in optimal combination and linear programming fields. It can be difficultly solved by the electronic computer in exponential level time. Meanwhile in previous studies deoxyribonucleic acid (DNA) molecular operations usually were used to solve NP-complete continuous path search problems, e.g. HPP, traveling salesman problem, rarely for NP-hard problems with discrete vertices or edges solutions, such as the minimum vertex cover problem, graph coloring problem and so on. In this paper, we present a DNA algorithm for solving the MMP with DNA molecular operations. For an undirected graph with $n$ vertices and $m$ edges, we reasonably design fixed length DNA strands representing vertices and edges of the graph, take appropriate steps and get the solutions of the MMP in proper length range using $O(n^3)$ time. We extend the application of DNA molecular operations and simultaneously simplify the complexity of the computation.

ordinary approach to quantum algorithm is based on quantum Turing machine or quantum circuits. It is known that this approach is not powerful enough to solve NP-complete problems. In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm.