Складність аналізу стійкості задач дискретного програмування з булевими змінними

Складність аналізу стійкості задач дискретного програмування з булевими змінними

Показано, що проблеми аналізу стійкості узагальнено близьких задач про покриття множинами та задач про багатовимірний булевий рюкзак є NP-складними. Це означає, що при незбіганні класів P і NP у найгіршому випадку не існує відповідних поліноміальних алгоритмів аналізу стійкості розглянутих класів уз...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Компьютерная математика
Datum:2015
1. Verfasser: Ліщук, Н.В.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schlagworte:
Теория и методы оптимизации
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/168369
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Складність аналізу стійкості задач дискретного програмування з булевими змінними / Н.В. Ліщук // Компьютерная математика. — 2015. — № 1. — С. 118-124. — Бібліогр.: 5 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-168369
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
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Складність аналізу стійкості задач дискретного програмування з булевими змінними
spellingShingle Складність аналізу стійкості задач дискретного програмування з булевими змінними
Ліщук, Н.В.
Теория и методы оптимизации
title_short Складність аналізу стійкості задач дискретного програмування з булевими змінними
title_full Складність аналізу стійкості задач дискретного програмування з булевими змінними
title_fullStr Складність аналізу стійкості задач дискретного програмування з булевими змінними
title_full_unstemmed Складність аналізу стійкості задач дискретного програмування з булевими змінними
title_sort складність аналізу стійкості задач дискретного програмування з булевими змінними
author Ліщук, Н.В.
author_facet Ліщук, Н.В.
topic Теория и методы оптимизации
topic_facet Теория и методы оптимизации
publishDate 2015
language Ukrainian
container_title Компьютерная математика
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Сложность анализа устойчивости задач дискретного программирования с булевыми переменными
Complexity of sensitivity analysis for discrete programming problems with boolean variables
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.
issn 2616-938Х
url https://nasplib.isofts.kiev.ua/handle/123456789/168369
citation_txt Складність аналізу стійкості задач дискретного програмування з булевими змінними / Н.В. Ліщук // Компьютерная математика. — 2015. — № 1. — С. 118-124. — Бібліогр.: 5 назв. — укр.
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
first_indexed 2025-12-07T18:49:55Z
last_indexed 2025-12-07T18:49:55Z
_version_ 1850876515430957056

Ähnliche Einträge