Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации
Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови P ≠ NP. Подібний результат виконується для задачі про...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/45150 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 2. — С. 134-141. — Бібліогр.: 10 назв. — рос. |
Репозиторії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Резюме: | Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови P ≠ NP. Подібний результат виконується для задачі про ранець. |
|---|