In 1985, to solve the computational knapsack problem, J.C. Lagarias and A.M. Odlyzhko have offered a method based on the reduction of this problem to the search of one of the short vector in the lattice of a special kind. This way allows to solve "almost all" knapsack problems that have a low density. In this paper the Lagarias — Odlyzhko method is modified to be applicable for solving the generalized knapsack problem and the systems of generalized knapsack problems. The system of knapsack problems is introduced hear as the finite set of the individual knapsack problems that have a common solution. Besides, for the generalized knapsack problem and for the systems of knapsack problems, some sets of density values are defined so that the modified methods allow to solve "almost all" generalized knapsack problems and the systems of knapsacks problems with the densities from these sets.
Download file
Counter downloads: 68
- Title Modification of the Lagarias — Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems
- Headline Modification of the Lagarias — Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(20)
- Date:
- DOI
Keywords
метод Лагариаса — Одлыжко, задача о рюкзаке, обобщённая задача о рюкзаке, системы задач о рюкзаках, Lagarias — Odlyzhko method, knapsack problem, generalized knapsack problem, systems of knapsack problemsAuthors
References
Coster M. J., Joux A., LaMacchia B. A., et al. Improved low-density subset sum algorithms // Computational Complexity. 1992. No. 2. P. 111-128.
Boas P. Another NP-complete problem and the complexity of computing short vectors in a lattice // Tech. rep. 8104, University of Amsterdam, Department of Mathematics, Netherlands, 1981. 10 p.
Brickell E. F. Solving low-density knapsacks // Advances in Cryptology. Proc. Crypto'83. Plenun Press, 1984. P. 25-37.
Odlyzko A.M. and Lagarias J. C. Solving low-density subset sum problems // J. Association for Computing Machinery. 1985. V.32. No. 1. P. 229-246.
Karp R. M. Reducibility among combinatorial problems // Complexity of Computer Computations. Plenum Press, 1972. P. 85-103.
Modification of the Lagarias — Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 2(20).
Download full-text version
Download fileCounter downloads: 192