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.展开更多
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.展开更多
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.展开更多
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.展开更多
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, 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.
基金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.
文摘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.
文摘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.
文摘NP(non-deterministic polynomial)证据加密(witness encryption,WE)是近来提出的一种新型的没有密钥生成过程的加密方案,可以用来构建许多其他的密码系统如公开密钥加密、IBE(identity based encryption)、ABE(attribute based encryption)等。该文提出WE的一种新应用:用WE构建可撤销广播加密系统,并且所构建的广播加密方案能支持简单的成员重加入功能(如付费电视);在构建的过程中指出以前的WE安全性定义不够严格,对原WE安全性定义进行了增强,并基于原WE方案和子集成员分辨难题、ROM(random oracle model)模型提出了一个新方案。
