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)

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

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

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

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

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

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

К вопросу о полиномиальной сложности проблемы эквивалентности в алгебраических моделях программ
von: Подловченко, Р.И.
Veröffentlicht: (2012)

Композиционно-номинативные аспекты адресного программирования
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: (2016)

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

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

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

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

О некоторых прикладных задачах марковских случайных процессов с локальным взаимодействием
von: Кнопов, П.С., et al.
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: (2008)

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

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

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

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

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

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

О мере изменения состояния коллектива взаимодействующих элементарных автоматов в дискретной среде
von: Курганский, А.Н.
Veröffentlicht: (2012)

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

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

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