О сложности одной задачи оптимизации упаковок - Трофимчук, А.Н.; Васянин, В.А.; Кузьменко, В.Н. (Кибернетика и системный анализ, 2016)
Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к ней NP-полной целочисленной задачи о многопродуктовом потоке минимальной стоимости.