|
This article is cited in 5 scientific papers (total in 5 papers)
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.
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
Linking options:
https://www.mathnet.ru/eng/zvmmf10945 https://www.mathnet.ru/eng/zvmmf/v59/i8/p1439
|
Statistics & downloads: |
Abstract page: | 168 | References: | 13 |
|