O(n) Procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates

Summary In this paper, we describe computationally efficient procedures for identifying all maximal cliques and non-dominated selected subsets of extensions of minimal covers and alternates that are implied by single 0–1 knapsack constraints. The induced inequalities are satisfied by and 0–1 feasible solution to the knapsack constraint, but are tipically violated by fractional solutions. In addition, the procedures described here are used in conjunction with other constraints to further tighten LP relaxations of 0–1 programs. The complexity of the procedures isO(n). Part of this work has been done while the author was at IBM Research, T.J. Watson Research Center, NY, USA.     

Approximation of min–max and min–max regret versions of some combinatorial optimization problems

This paper investigates, for the first time in the literature, the approximation of min–max (regret) versions of classical problems like shortest path, minimum spanning tree, and knapsack. For a constant number of scenarios, we establish fully polynomial-time approximation schemes for the min–max versions of these problems, using relationships between multi-objective and min–max optimization. Using dynamic programming and classical trimming techniques, we construct a fully polynomial-time approximation scheme for min–max regret shortest path. We also establish a fully polynomial-time approximation scheme for min–max regret spanning tree and prove that min–max regret knapsack is not at all approximable. For a non-constant number of scenarios, in which case min–max and min–max regret versions of polynomial-time solvable problems usually become strongly NP-hard, non-approximability results are provided for min–max (regret) versions of shortest path and spanning tree.     

A robust approach to the chance-constrained knapsack problem

In this paper, the chance-constrained knapsack problem (CKP) is addressed. Relying on robust optimization, a tractable combinatorial algorithm is proposed to solve approximately CKP. For two specific classes of uncertain knapsack problems, it is proved to solve CKP at optimality.     

A Public Key Cryptosystem Based On A Subgroup Membership Problem

We present a novel public key encryption scheme semantically secure in the standard model under the intractability assumption of a subgroup membership problem related to the factorization problem.Parts of this paper have already been published by the authors [13]AMS classification: 94A60     

基于认证测试的通用安全协议设计方法

以认证测试方法为基础,提出了一种通用的安全协议形式化设计方法,使用该方法对Needham-Schroeder(NS)公钥协议进行了重新设计.最后通过认证测试方法证明了重新设计的NS协议能够满足安全协议的保密性、身份认证和数据认证的要求,并且有效避免了原NS协议存在的中间人攻击问题.     

一种新的基于神经网络混沌吸引子的公钥密码算法

论述了一种新的基于神经网络混沌吸引子的公钥密码算法,在过饱和贮存的Hopfield神经网络模型中混沌吸引子与初始状态之间存在一种单向函数关系,改变神经网络的联结权矩阵,混沌吸引子及其相应的吸引域会随之发生改变,如果以联结权矩阵为陷门,并利用可交换的随机变换矩阵来改变神经网络的联结权矩阵,则可以创建一种新的Diffie-Hellman公钥加密算法．将随机变换矩阵作为私钥,而将变换后的神经网络联结突触矩阵作为公钥,介绍了这种新的公钥加密方案,并分析和讨论其安全性和加密效率。     

Knapsack problems with sigmoid utilities: Approximation algorithms via hybrid optimization

We study a class of non-convex optimization problems involving sigmoid functions. We show that sigmoid functions impart a combinatorial element to the optimization variables and make the global optimization computationally hard. We formulate versions of the knapsack problem, the generalized assignment problem and the bin-packing problem with sigmoid utilities. We merge approximation algorithms from discrete optimization with algorithms from continuous optimization to develop approximation algorithms for these NP-hard problems with sigmoid utilities.     

一种无证书的公平交换协议

公平交换协议是电子商务活动的一种重要安全协议.基于无证书密码体制,首先设计了一种无证书的可验证加密签名方案;然后基于该可验证加密签名方案构建了一种无证书的公平交换协议.协议降低了密钥托管和证书管理的开销,且满足有效性、公平性、时限性和优化性.     

Partially ordered knapsack and applications to scheduling

In the partially ordered knapsack problem (POK) we are given a set N of items and a partial order ?_P on N. Each item has a size and an associated weight. The objective is to pack a set N^′⊆N of maximum weight in a knapsack of bounded size. N^′ should be precedence-closed, i.e., be a valid prefix of ?_P. POK is a natural generalization, for which very little is known, of the classical Knapsack problem. In this paper we present both positive and negative results. We give an FPTAS for the important case of a two-dimensional partial order, a class of partial orders which is a substantial generalization of the series-parallel class, and we identify the first non-trivial special case for which a polynomial-time algorithm exists. Our results have implications for approximation algorithms for scheduling precedence-constrained jobs on a single machine to minimize the sum of weighted completion times, a problem closely related to POK.