Складність аналізу стійкості задач дискретного програмування з булевими змінними
Показано, що проблеми аналізу стійкості узагальнено близьких задач про покриття множинами та задач про багатовимірний булевий рюкзак є NP-складними. Це означає, що при незбіганні класів P і NP у найгіршому випадку не існує відповідних поліноміальних алгоритмів аналізу стійкості розглянутих класів уз...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2015 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/168369 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Складність аналізу стійкості задач дискретного програмування з булевими змінними / Н.В. Ліщук // Компьютерная математика. — 2015. — № 1. — С. 118-124. — Бібліогр.: 5 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862724907861803008 |
|---|---|
| author | Ліщук, Н.В. |
| author_facet | Ліщук, Н.В. |
| citation_txt | Складність аналізу стійкості задач дискретного програмування з булевими змінними / Н.В. Ліщук // Компьютерная математика. — 2015. — № 1. — С. 118-124. — Бібліогр.: 5 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Показано, що проблеми аналізу стійкості узагальнено близьких задач про покриття множинами та задач про багатовимірний булевий рюкзак є NP-складними. Це означає, що при незбіганні класів P і NP у найгіршому випадку не існує відповідних поліноміальних алгоритмів аналізу стійкості розглянутих класів узагальнено близьких задач (відрізняються одним елементом в матрицях обмежень або правих частинах).
Показано, что проблемы анализа устойчивости обобщенно близких задач о покрытии множествами и задач о многомерном булевом ранце являются NP-трудными. Это означает, что при несовпадении классов P и NP в наихудшем случае не существует соответствующих полиномиальных алгоритмов анализа сложности устойчивости рассмотренных классов обобщенно близких задач (отличаются одним элементом в матрицах ограничений либо в правых частях).
It is shown that the problems of sensitivity analysis for the generalized adjacent set covering problems and multivariate boolean knapsack problems are NP-hard. This implies that when the classes P and NP are mismatched, in worst case, the corresponding polynomial algorithms of sensitivity analysis for the classes of generally similar problems (differing in one element of matrices of constraints or in right hand sides) do not exist.
|
| first_indexed | 2025-12-07T18:49:55Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-168369 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2616-938Х |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:49:55Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Ліщук, Н.В. 2020-04-30T18:09:22Z 2020-04-30T18:09:22Z 2015 Складність аналізу стійкості задач дискретного програмування з булевими змінними / Н.В. Ліщук // Компьютерная математика. — 2015. — № 1. — С. 118-124. — Бібліогр.: 5 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168369 519.854.33 Показано, що проблеми аналізу стійкості узагальнено близьких задач про покриття множинами та задач про багатовимірний булевий рюкзак є NP-складними. Це означає, що при незбіганні класів P і NP у найгіршому випадку не існує відповідних поліноміальних алгоритмів аналізу стійкості розглянутих класів узагальнено близьких задач (відрізняються одним елементом в матрицях обмежень або правих частинах). Показано, что проблемы анализа устойчивости обобщенно близких задач о покрытии множествами и задач о многомерном булевом ранце являются NP-трудными. Это означает, что при несовпадении классов P и NP в наихудшем случае не существует соответствующих полиномиальных алгоритмов анализа сложности устойчивости рассмотренных классов обобщенно близких задач (отличаются одним элементом в матрицах ограничений либо в правых частях). It is shown that the problems of sensitivity analysis for the generalized adjacent set covering problems and multivariate boolean knapsack problems are NP-hard. This implies that when the classes P and NP are mismatched, in worst case, the corresponding polynomial algorithms of sensitivity analysis for the classes of generally similar problems (differing in one element of matrices of constraints or in right hand sides) do not exist. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Складність аналізу стійкості задач дискретного програмування з булевими змінними Сложность анализа устойчивости задач дискретного программирования с булевыми переменными Complexity of sensitivity analysis for discrete programming problems with boolean variables Article published earlier |
| spellingShingle | Складність аналізу стійкості задач дискретного програмування з булевими змінними Ліщук, Н.В. Теория и методы оптимизации |
| title | Складність аналізу стійкості задач дискретного програмування з булевими змінними |
| title_alt | Сложность анализа устойчивости задач дискретного программирования с булевыми переменными Complexity of sensitivity analysis for discrete programming problems with boolean variables |
| title_full | Складність аналізу стійкості задач дискретного програмування з булевими змінними |
| title_fullStr | Складність аналізу стійкості задач дискретного програмування з булевими змінними |
| title_full_unstemmed | Складність аналізу стійкості задач дискретного програмування з булевими змінними |
| title_short | Складність аналізу стійкості задач дискретного програмування з булевими змінними |
| title_sort | складність аналізу стійкості задач дискретного програмування з булевими змінними |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/168369 |
| work_keys_str_mv | AT líŝuknv skladnístʹanalízustíikostízadačdiskretnogoprogramuvannâzbulevimizmínnimi AT líŝuknv složnostʹanalizaustoičivostizadačdiskretnogoprogrammirovaniâsbulevymiperemennymi AT líŝuknv complexityofsensitivityanalysisfordiscreteprogrammingproblemswithbooleanvariables |