In this paper we present a classical parallel quantum algorithm for the satisfiability problem. We have exploited the classical parallelism of quantum algorithms developed in [G.L. Long and L. Xiao, Phys. Rev. A 69 （...In this paper we present a classical parallel quantum algorithm for the satisfiability problem. We have exploited the classical parallelism of quantum algorithms developed in [G.L. Long and L. Xiao, Phys. Rev. A 69 （2004） 052303], so that additional acceleration can be gained by using classical parallelism. The quantum algorithm first estimates the number of solutions using the quantum counting algorithm, and then by using the quantum searching algorithm, the explicit solutions are found.展开更多
The maximum satisfiability problem (MAX-SAT) refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weight of satisfied clauses) in a Boolean Formula. Most loca...The maximum satisfiability problem (MAX-SAT) refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weight of satisfied clauses) in a Boolean Formula. Most local search algorithms including tabu search rely on the 1-flip neighbourhood structure. In this work, we introduce a tabu search algorithm that makes use of the multilevel paradigm for solving MAX-SAT problems. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. This process aims at looking at the search as a multilevel process operating in a coarse-to-fine strategy evolving from k-flip neighbourhood to 1-flip neighbourhood-based structure. Experimental results comparing the multilevel tabu search against its single level variant are presented.展开更多
Cloud computing is a new and rapidly emerging computing paradigm where applications, data and IT services are provided over the Internet. The task-resource management is the key role in cloud computing systems. Task-r...Cloud computing is a new and rapidly emerging computing paradigm where applications, data and IT services are provided over the Internet. The task-resource management is the key role in cloud computing systems. Task-resource scheduling problems are premier which relate to the efficiency of the whole cloud computing facilities. Task-resource scheduling problem is NP-complete. In this paper, we consider an approach to solve this problem optimally. This approach is based on constructing a logical model for the problem. Using this model, we can apply algorithms for the satisfiability problem (SAT) to solve the task-resource scheduling problem. Also, this model allows us to create a testbed for particle swarm optimization algorithms for scheduling workflows.展开更多
基金supported by 973 Program under Grant No.2006CB921106National Natural Science Foundation of China under Grant No.60635040the Key Grant Project of the Ministry of Education under Grant No.306020
文摘In this paper we present a classical parallel quantum algorithm for the satisfiability problem. We have exploited the classical parallelism of quantum algorithms developed in [G.L. Long and L. Xiao, Phys. Rev. A 69 （2004） 052303], so that additional acceleration can be gained by using classical parallelism. The quantum algorithm first estimates the number of solutions using the quantum counting algorithm, and then by using the quantum searching algorithm, the explicit solutions are found.
文摘The maximum satisfiability problem (MAX-SAT) refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weight of satisfied clauses) in a Boolean Formula. Most local search algorithms including tabu search rely on the 1-flip neighbourhood structure. In this work, we introduce a tabu search algorithm that makes use of the multilevel paradigm for solving MAX-SAT problems. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. This process aims at looking at the search as a multilevel process operating in a coarse-to-fine strategy evolving from k-flip neighbourhood to 1-flip neighbourhood-based structure. Experimental results comparing the multilevel tabu search against its single level variant are presented.
基金partially supported by Analytical Departmental Program "Developing the Scientific Potential of Higher School"(Nos.2.1.1/14055 and 2.1.1/13995)
文摘Cloud computing is a new and rapidly emerging computing paradigm where applications, data and IT services are provided over the Internet. The task-resource management is the key role in cloud computing systems. Task-resource scheduling problems are premier which relate to the efficiency of the whole cloud computing facilities. Task-resource scheduling problem is NP-complete. In this paper, we consider an approach to solve this problem optimally. This approach is based on constructing a logical model for the problem. Using this model, we can apply algorithms for the satisfiability problem (SAT) to solve the task-resource scheduling problem. Also, this model allows us to create a testbed for particle swarm optimization algorithms for scheduling workflows.
