О сложности одной задачи оптимизации упаковок
Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/131394 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-131394 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1313942018-03-22T03:03:02Z О сложности одной задачи оптимизации упаковок Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н. Системный анализ Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является 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. 2016 Article О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/131394 519.854.2:004.023 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н. О сложности одной задачи оптимизации упаковок Кибернетика и системный анализ |
| description |
Рассмотрена задача оптимизации упаковок элементов квадратной матрицы, заданных целыми положительными числами, в блоки фиксированного размера. Предложена постановка задачи и исследована трудоемкость полного перебора ее решений. Доказано, что задача является NP-полной, путем полиномиального сведения к ней NP-полной целочисленной задачи о многопродуктовом потоке минимальной стоимости. |
| format |
Article |
| author |
Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н. |
| author_facet |
Трофимчук, А.Н. Васянин, В.А. Кузьменко, В.Н. |
| author_sort |
Трофимчук, А.Н. |
| title |
О сложности одной задачи оптимизации упаковок |
| title_short |
О сложности одной задачи оптимизации упаковок |
| title_full |
О сложности одной задачи оптимизации упаковок |
| title_fullStr |
О сложности одной задачи оптимизации упаковок |
| title_full_unstemmed |
О сложности одной задачи оптимизации упаковок |
| title_sort |
о сложности одной задачи оптимизации упаковок |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2016 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/131394 |
| citation_txt |
О сложности одной задачи оптимизации упаковок / А.Н. Трофимчук, В.А. Васянин, В.Н. Кузьменко // Кибернетика и системный анализ. — 2016. — Т. 52, № 1. — С. 83-92. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT trofimčukan osložnostiodnojzadačioptimizaciiupakovok AT vasâninva osložnostiodnojzadačioptimizaciiupakovok AT kuzʹmenkovn osložnostiodnojzadačioptimizaciiupakovok |
| first_indexed |
2023-10-18T21:02:06Z |
| last_indexed |
2023-10-18T21:02:06Z |
| _version_ |
1796151752088616960 |