Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации
Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови P ≠ NP. Подібний результат виконується для задачі про...
Збережено в:
| Видавець: | Інститут кібернетики ім. В.М. Глушкова НАН України |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/45150 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Цитувати: | Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 2. — С. 134-141. — Бібліогр.: 10 назв. — рос. |
Репозиторії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-45150 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-451502013-06-09T03:08:37Z Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации Михайлюк, В.А. Системный анализ Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови 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. 2010 Article Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 2. — С. 134-141. — Бібліогр.: 10 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45150 519.854 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Михайлюк, В.А. Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации Кибернетика и системный анализ |
| description |
Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови P ≠ NP. Подібний результат виконується для задачі про ранець. |
| format |
Article |
| author |
Михайлюк, В.А. |
| author_facet |
Михайлюк, В.А. |
| author_sort |
Михайлюк, В.А. |
| title |
Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_short |
Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_full |
Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_fullStr |
Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_full_unstemmed |
Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| title_sort |
общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2010 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/45150 |
| citation_txt |
Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 2. — С. 134-141. — Бібліогр.: 10 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT mihajlûkva obŝijpodhodkocenkesložnostipostoptimalʹnogoanalizadiskretnyhzadačoptimizacii |
| first_indexed |
2023-10-18T18:01:58Z |
| last_indexed |
2023-10-18T18:01:58Z |
| _version_ |
1796143139129393152 |