UDC 519.854.2:004.023

Complexity of one packing optimization problem

The authors consider the optimization of packing 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. Tabl.: 3. Refs: 8 titles.

УДК 519.854.2:004.023

Про складність однієї задачі оптимізації упакувань

Розглянуто задачу оптимізації упакувань елементів квадратної матриці, заданих цілими позитивними числами, у блоки фіксованого розміру. Запропоновано постановку задачі та досліджено трудомісткість повного перебору її розв’язків. Доведено, що задача є NP-повною. Це зроблено шляхом поліноміального зведення до неї NP-повної цілочисельної задачі про багатопродуктовий потік мінімальної вартості. Табл.: 3 Бібліогр.: 8 назв.

УДК 519.854.2:004.023

О сложности одной задачи оптимизации упаковок

Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к ней NP-полной целочисленной задачи о многопродуктовом потоке минимальной стоимости. Табл.: 3 Библиогр.: 8 назв.

Keywords:

packing optimization, integer multicommodity flow, labor input of exhaustive search, polynomial reducibility, NP-complete problems.


FULL TEXT

Author(s):

Трофимчук Александр Николаевич, чл.-кор. НАН Украины, профессор, заместитель директора Института телекоммуникаций и глобального информационного пространства НАН Украины, Киев,
e-mail: itelua@kv.ukrtel.net

Васянин Владимир Александрович, кандидат техн. наук, старший научный сотрудник Института телекоммуникаций и глобального информационного пространства НАН Украины, Киев,
e-mail:archukr@meta.ua

Кузьменко Виктор Николаевич, кандидат физ.-мат. наук, старший научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: kvnu@mail.ru