Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации
|
|
| Creator |
Михайлюк, В.А.
|
|
| Subject |
Кибернетика
|
|
| Description |
Показано, що поліноміального відносно . в середньому алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо відштовхуватися від оптимального розв’язку вихідної задачі, і DistNP не є підмножиною Average-P. Подібний результат виконується для задачі про ранець.
It is shown that an algorithm polynomial on the average with respect to to calculate the optimal solution of the set cover problem that differs from the original problem in one position of the constraint matrix doesn’t exist if the optimal solution of the original problem is known and unless DistNP subset of Average-P. A similar result is true for the knapsack problem. |
|
| Date |
2015-07-04T14:51:07Z
2015-07-04T14:51:07Z 2011 |
|
| Type |
Article
|
|
| Identifier |
Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 47-58. — Бібліогр.: 14 назв. — рос.
0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84250 519.854 |
|
| Language |
ru
|
|
| Relation |
Кибернетика и системный анализ
|
|
| Publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України
|
|