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

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

Показано, що проблеми аналізу стійкості узагальнено близьких задач про покриття множинами та задач про багатовимірний булевий рюкзак є 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.