Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации

Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации

Показано, що ZPP-, RP-ймовірнісних поліноміальних процедури постоптимального аналізу для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і ZPP ≠ NP (RP ≠...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Кибернетика и системный анализ
Дата:2012
Автор: Михайлюк, В.А.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Теми:
Кибернетика
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/84154
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 3-10. — Бібліогр.: 10 назв. — рос.

Репозитарії

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

Схожі ресурси