Buchumschlag

О сложности вычисления параметров устойчивости в задачах булева программирования

Показано, что для NP-полных задач трудоемким является даже вычисление шара устойчивости радиуса 1 оптимального решения (т.е. при P ≠ NP для этого не существует полиномиального алгоритма). При использовании жадных алгоритмов для задачи о покрытии множествами (задачи о ранце) при радиусе устойчивости...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Кибернетика и системный анализ
Datum:	2015
Hauptverfasser:	Михайлюк, В.А., Лищук, Н.В.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schlagworte:	Кибернетика
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/124906
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. — Т. 51, № 5. — С. 56-62. — Бібліогр.: 14 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

Ähnliche Einträge

Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования
von: Лищук, Н.В.
Veröffentlicht: (2015)

Анализ устойчивости задачи о ранце: один отрицательный результат
von: Михайлюк, В.А., et al.
Veröffentlicht: (2013)

Эволюционная модель задачи булева программирования
von: Козин, И.В.
Veröffentlicht: (2013)

Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации
von: Михайлюк, В.А.
Veröffentlicht: (2011)

Метод резолюции для анализа устойчивости задач 0-1 программирования
von: Михайлюк, В.А., et al.
Veröffentlicht: (2017)

О сложности анализа автоматов над конечным кольцом
von: Скобелев, В.В., et al.
Veröffentlicht: (2010)

Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений
von: Михайлюк, В.А.
Veröffentlicht: (2016)

Структурные модели алгоритмов в задачах прикладного программирования. II. Структурно-алгоритмический подход к моделированию программного обеспечения
von: Шинкаренко, В.И., et al.
Veröffentlicht: (2009)

Композиционно-номинативные аспекты адресного программирования
von: Никитченко, Н.С.
Veröffentlicht: (2009)

Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона
von: Николайчук, Я.Н., et al.
Veröffentlicht: (2014)

Метод вычисления семантической близости-связности между словами естественного языка
von: Анисимов, А.В., et al.
Veröffentlicht: (2011)

Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска
von: Шило, В.П., et al.
Veröffentlicht: (2011)

Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса
von: Коваленко, Н.С., et al.
Veröffentlicht: (2012)

Реоптимизация задачи о покрытии множествами
von: Михайлюк, В.А.
Veröffentlicht: (2010)

О пороге отношения аппроксимации для реоптимизации задачи о максимальном количестве выполненных уравнений в линейных системах над конечным полем
von: Михайлюк, В.А.
Veröffentlicht: (2012)

К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации
von: Михайлюк, В.А.
Veröffentlicht: (2011)

Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами
von: Михайлюк, В.А., et al.
Veröffentlicht: (2012)

Рекурсия и параллельные алгоритмы в задачах геометрического моделирования
von: Терещенко, В.Н., et al.
Veröffentlicht: (2010)

Групповые структуры на фактор-множествах в задачах классификации
von: Машталир, В.П., et al.
Veröffentlicht: (2014)

Построение оптимальных алгоритмов массовых вычислений в задачах цифровой фильтрации
von: Анисимов, А.В., et al.
Veröffentlicht: (2008)

Алгоритм декомпозиции геометрических объектов в 2D-задачах упаковки и раскроя
von: Стоян, Ю.Г., et al.
Veröffentlicht: (2011)

Интервальные вычисления в задачах оценки экспертных решений
von: Жуковская, О.А.
Veröffentlicht: (2012)

Об устойчивости по критерию векторных задач целочисленного квадратичного программирования
von: Лебедева, Т.Т., et al.
Veröffentlicht: (2003)

О сложности одной задачи оптимизации упаковок
von: Трофимчук, А.Н., et al.
Veröffentlicht: (2016)

Применение комбинированного метода выпуклого программирования в задачах финансовой математики
von: Бойко, В.В., et al.
Veröffentlicht: (2008)

Об оценках числовых характеристик сложности постоптимального анализа дискретных задач оптимизации
von: Михайлюк, В.А.
Veröffentlicht: (2010)

О работах киевской школы теоретической криптографии
von: Савчук, М.Н.
Veröffentlicht: (2010)

О двух последовательностях множеств отображений абстрактных множеств в дедекиндово кольцо
von: Скобелев, В.В.
Veröffentlicht: (2012)

О криптографических свойствах нового национального стандарта шифрования Украины
von: Алексейчук, А.Н., et al.
Veröffentlicht: (2016)

Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений
von: Лопатина, М.В.
Veröffentlicht: (2004)

О двух типах нелинейных автоматов над конечным кольцом
von: Скобелев, В.В.
Veröffentlicht: (2009)

О вычислительной стойкости квантовых алгоритмов преобразования информации
von: Скобелев, В.Г.
Veröffentlicht: (2010)

О некоторых множествах автоматов над конечным кольцом
von: Скобелев, В.Г.
Veröffentlicht: (2011)

О численном моделировании и оптимизации однонаправленных волновых процеcсов в неоднородных средах
von: Гладкий, А.В., et al.
Veröffentlicht: (2010)

Верификация UCM-спецификаций распределенных систем с использованием раскрашенных сетей Петри
von: Визовитин, Н.В., et al.
Veröffentlicht: (2015)

О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве
von: Емеличев, В.А., et al.
Veröffentlicht: (2010)

О гомоморфизме компонентной сети Петри
von: Лукьянова, Е.А.
Veröffentlicht: (2014)

Несколько замечаний о проблеме Коллатца
von: Рысцов, И.К.
Veröffentlicht: (2013)

О классе формул языка L*, специфицирующих автоматы с конечной памятью
von: Чеботарев, А.Н.
Veröffentlicht: (2010)

О влиянии потребительских предпочтений на равновесие в открытой экономической системе
von: Махорт, А.Ф.
Veröffentlicht: (2016)