Geodesic
Modification of the Lagarias–Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems
Prikladnaâ diskretnaâ matematika, no. 2 (2013), pp. 91-100 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: Lagarias–Odlyzhko method, knapsack problem, generalized knapsack problem, systems of knapsack problems. 
@article{PDM_2013_2_a9,
     author = {D. M. Murin},
     title = {Modification of the {Lagarias{\textendash}Odlyzhko} method for solving the generalized knapsack problem and the systems of knapsack problems},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {91--100},
     year = {2013},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_2_a9/}
}
TY  - JOUR
AU  - D. M. Murin
TI  - Modification of the Lagarias–Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 91
EP  - 100
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_2_a9/
LA  - ru
ID  - PDM_2013_2_a9
ER  - 
%0 Journal Article
%A D. M. Murin
%T Modification of the Lagarias–Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 91-100
%N 2
%U http://geodesic.mathdoc.fr/item/PDM_2013_2_a9/
%G ru
%F PDM_2013_2_a9
D. M. Murin. Modification of the Lagarias–Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems. Prikladnaâ diskretnaâ matematika, no. 2 (2013), pp. 91-100. http://geodesic.mathdoc.fr/item/PDM_2013_2_a9/

[1] Karp R. M., “Reducibility among combinatorial problems”, Complexity of Computer Computations, Plenum Press, 1972, 85–103 | DOI | MR

[2] Odlyzko A. M., Lagarias J. C., “Solving low-density subset sum problems”, J. Association for Computing Machinery, 32:1 (1985), 229–246 | DOI | MR | Zbl

[3] Brickell E. F., “Solving low-density knapsacks”, Advances in Cryptology, Proc. Crypto' 83, Plenun Press, 1984, 25–37 | DOI | MR

[4] 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 pp.

[5] Coster M. J., Joux A., LaMacchia B. A., et al., “Improved low-density subset sum algorithms”, Computational Complexity, 2:2 (1992), 111–128 | DOI | MR | Zbl