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

• 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
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: Складність аналізу стійкості задач дискретного програмування з булевими змінними / Н.В. Ліщук // Компьютерная математика. — 2015. — № 1. — С. 118-124. — Бібліогр.: 5 назв. — укр.

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