Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Zh. Vychisl. Mat. Mat. Fiz.:

Personal entry:
Save password
Forgotten password?

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

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
\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
\jour Comput. Math. Math. Phys.
\yr 2019
\vol 59
\issue 8
\pages 1380--1388

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