web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0000460183
Cybernetics and Systems Analysis   А - 2019 /  Issue (2016, Т. 52, № 1)
Трофимчук А. Н., Васянин В. А., Кузьменко В. Н.
О сложности одной задачи оптимизации упаковок Розглянуто задачу оптимізації упакувань елементів квадратної матриці, заданих цілими позитивними числами, у блоки фіксованого розміру. Запропоновано постановку задачі та досліджено трудомісткість повного перебору її розв'язків. Доведено, що задача є NP-повною. Це зроблено шляхом поліноміального зведення до неї NP-повної цілочислової задачі про багатопродуктовий потік мінімальної вартості.
 https://doi.org/10.1007/s10559-016-9802-9
 Scopus
Бібліографічний опис:
Трофимчук А. Н., Васянин В. А., Кузьменко В. Н. О сложности одной задачи оптимизации упаковок. Кибернетика и системный анализ. 2016. Т. 52, № 1. С. 83-92. doi: https://doi.org/10.1007/s10559-016-9802-9 URL: http://jnas.nbuv.gov.ua/article/UJRN-0000460183 |
 Cybernetics and Systems Analysis / Issue (2016, 52 (1))
Trofymchuk O.M.,
Vasyanin V.A.,
Kuzmenko V.N.
Complexity of one packing optimization problem The authors consider packing optimization for elements of a square matrix, which are given by positive integers, into blocks of fixed size. The problem is formulated and its combinatorial intractability is discussed. The problem is proved to be NP-complete. This is done by polynomial reduction of an NP-complete minimum-cost integer multicommodity flow problem to this problem. © 2016, Springer Science+Business Media New York. Keywords: integer multicommodity flow, labor input of exhaustive search, NP-complete problems, packing optimization, polynomial reducibility, Computational complexity, Integer programming, Polynomials, Integer multicommodity flow problem, Minimum cost, Multi-commodity flow, NP Complete, Packing optimization, Polynomial reduction, Positive integers, Square matrices, Optimization
Cite:
Trofymchuk O.M.,
Vasyanin V.A.,
Kuzmenko V.N.
(2016). Complexity of one packing optimization problem. Cybernetics and Systems Analysis, 52 (1), 83-92. doi: https://doi.org/10.1007/s10559-016-9802-9 http://jnas.nbuv.gov.ua/article/UJRN-0000460183 [In Russian]. |
PDF