Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации
Показано, що ZPP-, RP-ймовірнісних поліноміальних процедури постоптимального аналізу для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і ZPP ≠ NP (RP ≠...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2012 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84154 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 3-10. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84154 |
|---|---|
| record_format |
dspace |
| spelling |
Михайлюк, В.А. 2015-07-03T10:44:25Z 2015-07-03T10:44:25Z 2012 Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 3-10. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84154 519.854 Показано, що ZPP-, RP-ймовірнісних поліноміальних процедури постоптимального аналізу для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і ZPP ≠ NP (RP ≠ NP). Подібний результат маємо для задачі про ранець. It is shown that a ZPP-, RP-probabilistic polynomial procedures of postoptimality analysis for finding the optimal solution of a set cover problem that differs from the original problem in one position of matrix of constraints do not exist if the optimal solution of the original problem is known and if ZPP ≠ NP (RP ≠ NP) A similar result holds for the knapsack problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации Підхід до оцінки складності ймовірнісних процедур постоптимального аналізу дискретних задач оптимізації An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of 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 |
2012 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Підхід до оцінки складності ймовірнісних процедур постоптимального аналізу дискретних задач оптимізації An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems |
| description |
Показано, що ZPP-, RP-ймовірнісних поліноміальних процедури постоптимального аналізу для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і ZPP ≠ NP (RP ≠ NP). Подібний результат маємо для задачі про ранець.
It is shown that a ZPP-, RP-probabilistic polynomial procedures of postoptimality analysis for finding the optimal solution of a set cover problem that differs from the original problem in one position of matrix of constraints do not exist if the optimal solution of the original problem is known and if ZPP ≠ NP (RP ≠ NP) A similar result holds for the knapsack problem.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84154 |
| citation_txt |
Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 3-10. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT mihailûkva podhodkocenkesložnostiveroâtnostnyhprocedurpostoptimalʹnogoanalizadiskretnyhzadačoptimizacii AT mihailûkva pídhíddoocínkiskladnostíimovírnísnihprocedurpostoptimalʹnogoanalízudiskretnihzadačoptimízacíí AT mihailûkva anapproachtoestimatingthecomplexityofprobabilisticproceduresforthepostoptimalityanalysisofdiscreteoptimizationproblems |
| first_indexed |
2025-12-07T20:13:30Z |
| last_indexed |
2025-12-07T20:13:30Z |
| _version_ |
1850881773428277248 |