RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Prikl. Diskr. Mat., 2013, Number 2(20), Pages 91–100 (Mi pdm411)

Computational Methods in Discrete Mathematics

Modification of the Lagarias–Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems

D. M. Murin

Demidov Yaroslavl State University, Yaroslavl, Russia

Abstract: 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.

Full text: PDF file (581 kB)
References: PDF file   HTML file
UDC: 511

Citation: D. M. Murin, “Modification of the Lagarias–Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems”, Prikl. Diskr. Mat., 2013, no. 2(20), 91–100

Citation in format AMSBIB
\Bibitem{Mur13} \by D.~M.~Murin \paper Modification of the Lagarias--Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems \jour Prikl. Diskr. Mat. \yr 2013 \issue 2(20) \pages 91--100 \mathnet{http://mi.mathnet.ru/pdm411}