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

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

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Кибернетика и системный анализ
Datum:2016
Hauptverfasser: Трофимчук, А.Н., Васянин, В.А., Кузьменко, В.Н.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Schlagworte:
Системный анализ
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/131394
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-131394
record_format dspace
spelling Трофимчук, А.Н.
Васянин, В.А.
Кузьменко, В.Н.
2018-03-21T20:33:21Z
2018-03-21T20:33:21Z
2016
О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос.
0023-1274
https://nasplib.isofts.kiev.ua/handle/123456789/131394
519.854.2:004.023
Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к ней NP-полной целочисленной задачи о многопродуктовом потоке минимальной стоимости.
Розглянуто задачу оптимізації упакувань елементів квадратної матриці, заданих цілими позитивними числами, у блоки фіксованого розміру. Запропоновано постановку задачі та досліджено трудомісткість повного перебору її розв’язків. Доведено, що задача є NP-повною. Це зроблено шляхом поліноміального зведення до неї NP-повної цілочисельної задачі про багатопродуктовий потік мінімальної вартості.
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.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Кибернетика и системный анализ
Системный анализ
О сложности одной задачи оптимизации упаковок
Про складність однієї задачі оптимізації упакувань
Complexity of one packing optimization problem
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title О сложности одной задачи оптимизации упаковок
spellingShingle О сложности одной задачи оптимизации упаковок
Трофимчук, А.Н.
Васянин, В.А.
Кузьменко, В.Н.
Системный анализ
title_short О сложности одной задачи оптимизации упаковок
title_full О сложности одной задачи оптимизации упаковок
title_fullStr О сложности одной задачи оптимизации упаковок
title_full_unstemmed О сложности одной задачи оптимизации упаковок
title_sort о сложности одной задачи оптимизации упаковок
author Трофимчук, А.Н.
Васянин, В.А.
Кузьменко, В.Н.
author_facet Трофимчук, А.Н.
Васянин, В.А.
Кузьменко, В.Н.
topic Системный анализ
topic_facet Системный анализ
publishDate 2016
language Russian
container_title Кибернетика и системный анализ
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Про складність однієї задачі оптимізації упакувань
Complexity of one packing optimization problem
description Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к ней NP-полной целочисленной задачи о многопродуктовом потоке минимальной стоимости. Розглянуто задачу оптимізації упакувань елементів квадратної матриці, заданих цілими позитивними числами, у блоки фіксованого розміру. Запропоновано постановку задачі та досліджено трудомісткість повного перебору її розв’язків. Доведено, що задача є NP-повною. Це зроблено шляхом поліноміального зведення до неї NP-повної цілочисельної задачі про багатопродуктовий потік мінімальної вартості. 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.
issn 0023-1274
url https://nasplib.isofts.kiev.ua/handle/123456789/131394
citation_txt О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос.
work_keys_str_mv AT trofimčukan osložnostiodnoizadačioptimizaciiupakovok
AT vasâninva osložnostiodnoizadačioptimizaciiupakovok
AT kuzʹmenkovn osložnostiodnoizadačioptimizaciiupakovok
AT trofimčukan proskladnístʹodníêízadačíoptimízacííupakuvanʹ
AT vasâninva proskladnístʹodníêízadačíoptimízacííupakuvanʹ
AT kuzʹmenkovn proskladnístʹodníêízadačíoptimízacííupakuvanʹ
AT trofimčukan complexityofonepackingoptimizationproblem
AT vasâninva complexityofonepackingoptimizationproblem
AT kuzʹmenkovn complexityofonepackingoptimizationproblem
first_indexed 2025-12-07T18:00:15Z
last_indexed 2025-12-07T18:00:15Z
_version_ 1850873391015264256

Ähnliche Einträge