Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
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



Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find






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


Zh. Vychisl. Mat. Mat. Fiz., 2019, Volume 59, Number 8, Pages 1439–1447 (Mi zvmmf10945)  

This article is cited in 1 scientific paper (total in 1 paper)

On combinatorial properties of the knapsack problem

E. N. Gordeevab, V. K. Leont'evab

a Bauman State Technical University, Moscow, 105005 Russia
b Dorodnicyn Computing Center, Federal Research Center "Computer Science and Control," Russian Academy of Sciences, Moscow, 119333 Russia

Abstract: The knapsack problem with Boolean variables and a single constraint is studied. In the general case, this problem is NP-hard; for this reason, its exact solution requires the use of various search algorithms with the decomposition of the set of feasible solutions and computation of estimates of the objective function. Combinatorial formulas for computing and estimating the value of the objective function in various cases depending on the set of given parameters of the problem are derived. The case when the coefficients of the constraint vector coincide with the coefficients of the objective function is considered. The relationship between the set of solutions of the problem and threshold functions of a certain type is revealed. The coefficients of the objective function, the coefficients of the constraint vector, and the knapsack size are used as parameters. The classical method of generating functions is used as the basic technique. The results obtained in this paper can be used, in particular, for estimating the complexity of search and decomposition methods of solving the problem and for developing such methods as auxiliary procedures.

Key words: knapsack problem, generating functions, NP-hard problems, estimate of the objective function.

Funding Agency Grant Number
Russian Academy of Sciences - Federal Agency for Scientific Organizations 0063-2016-0003


DOI: https://doi.org/10.1134/S0044466919080076


English version:
Computational Mathematics and Mathematical Physics, 2019, 59:8, 1380–1388

Bibliographic databases:

UDC: 519.16
Received: 19.12.2018
Revised: 02.02.2019
Accepted:08.02.2019

Citation: E. N. Gordeev, V. K. Leont'ev, “On combinatorial properties of the knapsack problem”, Zh. Vychisl. Mat. Mat. Fiz., 59:8 (2019), 1439–1447; Comput. Math. Math. Phys., 59:8 (2019), 1380–1388

Citation in format AMSBIB
\Bibitem{GorLeo19}
\by E.~N.~Gordeev, V.~K.~Leont'ev
\paper On combinatorial properties of the knapsack problem
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2019
\vol 59
\issue 8
\pages 1439--1447
\mathnet{http://mi.mathnet.ru/zvmmf10945}
\crossref{https://doi.org/10.1134/S0044466919080076}
\elib{https://elibrary.ru/item.asp?id=39149038}
\transl
\jour Comput. Math. Math. Phys.
\yr 2019
\vol 59
\issue 8
\pages 1380--1388
\crossref{https://doi.org/10.1134/S0965542519080074}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000487804000015}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85073198529}


Linking options:
  • http://mi.mathnet.ru/eng/zvmmf10945
  • http://mi.mathnet.ru/eng/zvmmf/v59/i8/p1439

    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

    This publication is cited in the following articles:
    1. V. K. Leontev, E. N. Gordeev, “O chisle reshenii sistemy bulevykh uravnenii”, Avtomat. i telemekh., 2021, no. 9, 150–168  mathnet  crossref
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:71

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