Prikladnaya Diskretnaya Matematika
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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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}


Linking options:
  • http://mi.mathnet.ru/eng/pdm411
  • http://mi.mathnet.ru/eng/pdm/y2013/i2/p91

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Number of views:
    This page:296
    Full text:109
    References:29

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021