Кібернетика і Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
Розглянуто задачу оптимізації упакувань елементів квадратної матриці, заданих цілими позитивними числами, у блоки фіксованого розміру. Запропоновано постановку задачі та досліджено трудомісткість повного перебору її розв’язків. Доведено, що задача є NP-повною. Це зроблено шляхом поліноміального зведення до неї NP-повної цілочисельної задачі про багатопродуктовий потік мінімальної вартості. Табл.: 3 Бібліогр.: 8 назв.
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.
Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к ней NP-полной целочисленной задачи о многопродуктовом потоке минимальной стоимости.Табл.: 3 Библиогр.: 8 назв.
Трофимчук Александр Николаевич, чл.-кор. НАН Украины, профессор,
заместитель директора Института телекоммуникаций и глобального информационного пространства НАН Украины, Киев,
e-mail: itelua@kv.ukrtel.net
Васянин Владимир Александрович, кандидат техн. наук, старший научный сотрудник Института телекоммуникаций
и глобального информационного пространства НАН Украины, Киев,
e-mail: archukr@meta.ua
Кузьменко Виктор Николаевич, кандидат физ.-мат. наук, старший научный сотрудник Института кибернетики
им. В.М. Глушкова НАН Украины, Киев,
e-mail: kvnu@mail.ru
