With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm...With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm for solving NP hard problems. In this paper we deal with a famous example , the well known NP hard problem——Circles Packing. It shows that our algorithm is dramatically very efficient. We are inspired that, the concrete physics algorithm will always be very efficient for NP hard problem.展开更多
Many heuristic search methods exhibit a remarkable variability in the time required to solve some particular problem instances. Their cost distributions are often heavy-tailed. It has been demonstrated that, in most c...Many heuristic search methods exhibit a remarkable variability in the time required to solve some particular problem instances. Their cost distributions are often heavy-tailed. It has been demonstrated that, in most cases, rapid restart (RR) method can prominently suppress the heavy-tailed nature of the instances and improve computation efficiency. However, it is usually time-consuming to check whether an algorithm on a specific instance is heavy-tailed or not. Moreover, if the heavy-tailed distribution is confirmed and the RR method is relevant, an optimal RR threshold should be chosen to facilitate the RR mechanism. In this paper, an approximate approach is proposed to quickly check whether an algorithm on a specific instance is heavy-tailed or not. The method is realized by means of calculating the maximal Lyapunov exponent of its generic running trace. Then a statistical formula to estimate the optimal RR threshold is educed. The method is based on common nonparametric estimation, e.g., Kernel estimation. Two heuristic methods are selected to verify our method. The experimental results are consistent with the theoretical consideration perfectly.展开更多
In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' ...In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' of the job on position i and a “normal' processing time of the job. The criteria considered is to minimize scheduled length of all jobs. A lemma is proposed and proved. In no deadline constrained condition, the problem belongs to polynomial time algorithm. It is proved by using 3 partition that if the problem is deadline constrained, its complexity is strong NP hard. Finally, a conjuncture is proposed that is to be proved.展开更多
基于强化学习的最大公共诱导子图(Maximum Common Induced Subgraph,MCIS)算法在处理历史搜索中低频出现的顶点时存在局限,难以评估其真实重要性并进行有效探索。为此,提出一种基于动作与环境反馈的前向预测方法。动作反馈通过奖励机制...基于强化学习的最大公共诱导子图(Maximum Common Induced Subgraph,MCIS)算法在处理历史搜索中低频出现的顶点时存在局限,难以评估其真实重要性并进行有效探索。为此,提出一种基于动作与环境反馈的前向预测方法。动作反馈通过奖励机制量化分支顶点的剪枝效果,环境反馈则用双域个数来表征待搜索子图的大小。前向预测通过单边采样选择顶点模拟分支,并根据反馈确定最佳顶点。实验结果表明,新算法McSplitLA比McSplitDAL多解决7个算例,平均求解时间减少11.2%~17.9%,有效提高了剪枝率并优化了探索方向。展开更多
NP(non-deterministic polynomial)证据加密(witness encryption,WE)是近来提出的一种新型的没有密钥生成过程的加密方案,可以用来构建许多其他的密码系统如公开密钥加密、IBE(identity based encryption)、ABE(attribute based encrypt...NP(non-deterministic polynomial)证据加密(witness encryption,WE)是近来提出的一种新型的没有密钥生成过程的加密方案,可以用来构建许多其他的密码系统如公开密钥加密、IBE(identity based encryption)、ABE(attribute based encryption)等。该文提出WE的一种新应用:用WE构建可撤销广播加密系统,并且所构建的广播加密方案能支持简单的成员重加入功能(如付费电视);在构建的过程中指出以前的WE安全性定义不够严格,对原WE安全性定义进行了增强,并基于原WE方案和子集成员分辨难题、ROM(random oracle model)模型提出了一个新方案。展开更多
In this paper, a recently developed nature-inspired optimization algorithm called the hydrological cycle algorithm (HCA) is evaluated on the traveling salesman problem (TSP). The HCA is based on the continuous movemen...In this paper, a recently developed nature-inspired optimization algorithm called the hydrological cycle algorithm (HCA) is evaluated on the traveling salesman problem (TSP). The HCA is based on the continuous movement of water drops in the natural hydrological cycle. The HCA performance is tested on various geometric structures and standard benchmarks instances. The HCA has successfully solved TSPs and obtained the optimal solution for 20 of 24 benchmarked instances, and near-optimal for the rest. The obtained results illustrate the efficiency of using HCA for solving discrete domain optimization problems. The solution quality and number of iterations were compared with those of other metaheuristic algorithms. The comparisons demonstrate the effectiveness of the HCA.展开更多
In this paper, single machine scheduling problems with variable processing time are raised. The criterions of the problem considered are minimizing scheduling length of all jobs, flow time and number of tardy jobs and...In this paper, single machine scheduling problems with variable processing time are raised. The criterions of the problem considered are minimizing scheduling length of all jobs, flow time and number of tardy jobs and so on. The complexity of the problem is determined. [WT5HZ]展开更多
Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging withou...Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O（2^3n/8） time when O（2^3n/8） shared memory units and O（2^n/4） processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-fist algorithm is the first exclusive-read exclusive-write （EREW） parallel algorithm that can solve the knapsack instances in less than O（2^n/2） time when the available hardware resource is smaller than O（2^n/2） , and hence is an improved result over the past researches.展开更多
The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved ...The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved by 3 partition problem that if the problem is of ready time and common deadline constrained, its complexity is NP hard in the strong sense. Finally, a polynomial algorithm for solving unit processing time and common deadline problems is proposed.展开更多
In this paper, we first reformulate the max-min dispersion problem as a saddle-point problem. Specifically, we introduce an auxiliary problem whose optimum value gives an upper bound on that of the original problem. T...In this paper, we first reformulate the max-min dispersion problem as a saddle-point problem. Specifically, we introduce an auxiliary problem whose optimum value gives an upper bound on that of the original problem. Then we propose the saddle-point problem to be solved by an adaptive custom proximal point algorithm. Numerical results show that the proposed algorithm is efficient.展开更多
基金86 3National High-Tech Program of China(86 3-30 6 -0 5 -0 3-1) National Natural Science Foundation of China(193310 5 0 ) Chi
文摘With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm for solving NP hard problems. In this paper we deal with a famous example , the well known NP hard problem——Circles Packing. It shows that our algorithm is dramatically very efficient. We are inspired that, the concrete physics algorithm will always be very efficient for NP hard problem.
文摘Many heuristic search methods exhibit a remarkable variability in the time required to solve some particular problem instances. Their cost distributions are often heavy-tailed. It has been demonstrated that, in most cases, rapid restart (RR) method can prominently suppress the heavy-tailed nature of the instances and improve computation efficiency. However, it is usually time-consuming to check whether an algorithm on a specific instance is heavy-tailed or not. Moreover, if the heavy-tailed distribution is confirmed and the RR method is relevant, an optimal RR threshold should be chosen to facilitate the RR mechanism. In this paper, an approximate approach is proposed to quickly check whether an algorithm on a specific instance is heavy-tailed or not. The method is realized by means of calculating the maximal Lyapunov exponent of its generic running trace. Then a statistical formula to estimate the optimal RR threshold is educed. The method is based on common nonparametric estimation, e.g., Kernel estimation. Two heuristic methods are selected to verify our method. The experimental results are consistent with the theoretical consideration perfectly.
文摘In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' of the job on position i and a “normal' processing time of the job. The criteria considered is to minimize scheduled length of all jobs. A lemma is proposed and proved. In no deadline constrained condition, the problem belongs to polynomial time algorithm. It is proved by using 3 partition that if the problem is deadline constrained, its complexity is strong NP hard. Finally, a conjuncture is proposed that is to be proved.
文摘基于强化学习的最大公共诱导子图(Maximum Common Induced Subgraph,MCIS)算法在处理历史搜索中低频出现的顶点时存在局限,难以评估其真实重要性并进行有效探索。为此,提出一种基于动作与环境反馈的前向预测方法。动作反馈通过奖励机制量化分支顶点的剪枝效果,环境反馈则用双域个数来表征待搜索子图的大小。前向预测通过单边采样选择顶点模拟分支,并根据反馈确定最佳顶点。实验结果表明,新算法McSplitLA比McSplitDAL多解决7个算例,平均求解时间减少11.2%~17.9%,有效提高了剪枝率并优化了探索方向。
文摘NP(non-deterministic polynomial)证据加密(witness encryption,WE)是近来提出的一种新型的没有密钥生成过程的加密方案,可以用来构建许多其他的密码系统如公开密钥加密、IBE(identity based encryption)、ABE(attribute based encryption)等。该文提出WE的一种新应用:用WE构建可撤销广播加密系统,并且所构建的广播加密方案能支持简单的成员重加入功能(如付费电视);在构建的过程中指出以前的WE安全性定义不够严格,对原WE安全性定义进行了增强,并基于原WE方案和子集成员分辨难题、ROM(random oracle model)模型提出了一个新方案。
文摘In this paper, a recently developed nature-inspired optimization algorithm called the hydrological cycle algorithm (HCA) is evaluated on the traveling salesman problem (TSP). The HCA is based on the continuous movement of water drops in the natural hydrological cycle. The HCA performance is tested on various geometric structures and standard benchmarks instances. The HCA has successfully solved TSPs and obtained the optimal solution for 20 of 24 benchmarked instances, and near-optimal for the rest. The obtained results illustrate the efficiency of using HCA for solving discrete domain optimization problems. The solution quality and number of iterations were compared with those of other metaheuristic algorithms. The comparisons demonstrate the effectiveness of the HCA.
文摘In this paper, single machine scheduling problems with variable processing time are raised. The criterions of the problem considered are minimizing scheduling length of all jobs, flow time and number of tardy jobs and so on. The complexity of the problem is determined. [WT5HZ]
文摘Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O（2^3n/8） time when O（2^3n/8） shared memory units and O（2^n/4） processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-fist algorithm is the first exclusive-read exclusive-write （EREW） parallel algorithm that can solve the knapsack instances in less than O（2^n/2） time when the available hardware resource is smaller than O（2^n/2） , and hence is an improved result over the past researches.
文摘The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved by 3 partition problem that if the problem is of ready time and common deadline constrained, its complexity is NP hard in the strong sense. Finally, a polynomial algorithm for solving unit processing time and common deadline problems is proposed.
文摘In this paper, we first reformulate the max-min dispersion problem as a saddle-point problem. Specifically, we introduce an auxiliary problem whose optimum value gives an upper bound on that of the original problem. Then we propose the saddle-point problem to be solved by an adaptive custom proximal point algorithm. Numerical results show that the proposed algorithm is efficient.
