Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации
Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови P ≠ NP. Подібний результат виконується для задачі про...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45150 |
| 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: | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 2. — С. 134-141. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862747264131268608 |
|---|---|
| author | Михайлюк, В.А. |
| author_facet | Михайлюк, В.А. |
| citation_txt | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 2. — С. 134-141. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови P ≠ NP. Подібний результат виконується для задачі про ранець.
It is shown that there does not exist a polynomial algorithm to derive the optimal solution of a set cover problem that differs from the original problem in one position of the matrix of constraints if the optimal solution of original problem is known and unlessP NP. A similar result holds for a knapsack problem.
|
| first_indexed | 2025-12-07T20:50:06Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-45150 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T20:50:06Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.А. 2013-06-08T06:47:14Z 2013-06-08T06:47:14Z 2010 Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 2. — С. 134-141. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45150 519.854 Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови P ≠ NP. Подібний результат виконується для задачі про ранець. It is shown that there does not exist a polynomial algorithm to derive the optimal solution of a set cover problem that differs from the original problem in one position of the matrix of constraints if the optimal solution of original problem is known and unlessP NP. A similar result holds for a knapsack problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации Загальний підхід до оцінки складності постоптимального аналізу дискретних задач оптимізації General approach to estimating the complexity of postoptimality analysis for discrete optimization problems Article published earlier |
| spellingShingle | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации Михайлюк, В.А. Системный анализ |
| title | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_alt | Загальний підхід до оцінки складності постоптимального аналізу дискретних задач оптимізації General approach to estimating the complexity of postoptimality analysis for discrete optimization problems |
| title_full | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_fullStr | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_full_unstemmed | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_short | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_sort | общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45150 |
| work_keys_str_mv | AT mihailûkva obŝiipodhodkocenkesložnostipostoptimalʹnogoanalizadiskretnyhzadačoptimizacii AT mihailûkva zagalʹniipídhíddoocínkiskladnostípostoptimalʹnogoanalízudiskretnihzadačoptimízacíí AT mihailûkva generalapproachtoestimatingthecomplexityofpostoptimalityanalysisfordiscreteoptimizationproblems |