Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации
Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови 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| Summary: | Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови 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.
|
|---|---|
| ISSN: | 0023-1274 |