Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации
Показано, що поліноміального відносно . в середньому алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо відштовхуватися від оптимального розв’язку вихідної задачі, і DistNP не є підмножиною Av...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2011 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84250 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 47-58. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84250 |
|---|---|
| record_format |
dspace |
| spelling |
Михайлюк, В.А. 2015-07-04T14:51:07Z 2015-07-04T14:51:07Z 2011 Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 47-58. — Бібліогр.: 14 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84250 519.854 Показано, що поліноміального відносно . в середньому алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо відштовхуватися від оптимального розв’язку вихідної задачі, і 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации Підхід до оцінки складності в середньому постоптимального аналізу дискретних задач оптимізації An approach to estimating the average-case complexity of postoptimality analysis for discrete optimization problems 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 |
2011 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Підхід до оцінки складності в середньому постоптимального аналізу дискретних задач оптимізації An approach to estimating the average-case complexity of postoptimality analysis for discrete optimization problems |
| 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.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84250 |
| citation_txt |
Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 47-58. — Бібліогр.: 14 назв. — рос. |
| work_keys_str_mv |
AT mihailûkva podhodkocenkesložnostivsrednempostoptimalʹnogoanalizadiskretnyhzadačoptimizacii AT mihailûkva pídhíddoocínkiskladnostívserednʹomupostoptimalʹnogoanalízudiskretnihzadačoptimízacíí AT mihailûkva anapproachtoestimatingtheaveragecasecomplexityofpostoptimalityanalysisfordiscreteoptimizationproblems |
| first_indexed |
2025-12-07T16:04:11Z |
| last_indexed |
2025-12-07T16:04:11Z |
| _version_ |
1850866088329347072 |