Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 2

knapsack problem Related Publications

2 A New Knapsack Public-Key Cryptosystem Based on Permutation Combination Algorithm

Authors: Cheng-Chi Lee, Min-Shiang Hwang, Shiang-Feng Tzeng

Abstract:

A new secure knapsack cryptosystem based on the Merkle-Hellman public key cryptosystem will be proposed in this paper. Although it is common sense that when the density is low, the knapsack cryptosystem turns vulnerable to the low-density attack. The density d of a secure knapsack cryptosystem must be larger than 0.9408 to avoid low-density attack. In this paper, we investigate a new Permutation Combination Algorithm. By exploiting this algorithm, we shall propose a novel knapsack public-key cryptosystem. Our proposed scheme can enjoy a high density to avoid the low-density attack. The density d can also exceed 0.9408 to avoid the low-density attack.

Keywords: public key, knapsack problem, Knapsack cryptosystem, low-density attack

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1514
1 A Comparison of Exact and Heuristic Approaches to Capital Budgeting

Authors: Miloš Šeda, Jindřiška Šedová

Abstract:

This paper summarizes and compares approaches to solving the knapsack problem and its known application in capital budgeting. The first approach uses deterministic methods and can be applied to small-size tasks with a single constraint. We can also apply commercial software systems such as the GAMS modelling system. However, because of NP-completeness of the problem, more complex problem instances must be solved by means of heuristic techniques to achieve an approximation of the exact solution in a reasonable amount of time. We show the problem representation and parameter settings for a genetic algorithm framework.

Keywords: Genetic Algorithm, Capital Budgeting, knapsack problem, GAMS, heuristic method

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1384