О сложности одной задачи оптимизации упаковок
Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2016 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| 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| _version_ | 1862715741693804544 |
|---|---|
| author | Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н. |
| author_facet | Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н. |
| citation_txt | О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| 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.
|
| first_indexed | 2025-12-07T18:00:15Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-131394 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:00:15Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
| spellingShingle | О сложности одной задачи оптимизации упаковок Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н. Системный анализ |
| title | О сложности одной задачи оптимизации упаковок |
| title_alt | Про складність однієї задачі оптимізації упакувань Complexity of one packing optimization problem |
| title_full | О сложности одной задачи оптимизации упаковок |
| title_fullStr | О сложности одной задачи оптимизации упаковок |
| title_full_unstemmed | О сложности одной задачи оптимизации упаковок |
| title_short | О сложности одной задачи оптимизации упаковок |
| title_sort | о сложности одной задачи оптимизации упаковок |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/131394 |
| 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 |