Зображення обкладинки

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

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

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Кибернетика и системный анализ
Дата:	2015
Автори:	Михайлюк, В.А., Лищук, Н.В.
Формат:	Стаття
Мова:	Російська
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Теми:	Кибернетика
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/124906
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	О сложности вычисления параметров устойчивости в задачах булева программирования / В.А. Михайлюк, Н.В. Лищук // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 56-62. — Бібліогр.: 14 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

Схожі ресурси

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

Анализ устойчивости задачи о ранце: один отрицательный результат
за авторством: Михайлюк, В.А., та інші
Опубліковано: (2013)

Эволюционная модель задачи булева программирования
за авторством: Козин, И.В.
Опубліковано: (2013)

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

Метод резолюции для анализа устойчивости задач 0-1 программирования
за авторством: Михайлюк, В.А., та інші
Опубліковано: (2017)

О сложности анализа автоматов над конечным кольцом
за авторством: Скобелев, В.В., та інші
Опубліковано: (2010)

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

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

Композиционно-номинативные аспекты адресного программирования
за авторством: Никитченко, Н.С.
Опубліковано: (2009)

Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона
за авторством: Николайчук, Я.Н., та інші
Опубліковано: (2014)

Метод вычисления семантической близости-связности между словами естественного языка
за авторством: Анисимов, А.В., та інші
Опубліковано: (2011)

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

Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса
за авторством: Коваленко, Н.С., та інші
Опубліковано: (2012)

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

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

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

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

Рекурсия и параллельные алгоритмы в задачах геометрического моделирования
за авторством: Терещенко, В.Н., та інші
Опубліковано: (2010)

Групповые структуры на фактор-множествах в задачах классификации
за авторством: Машталир, В.П., та інші
Опубліковано: (2014)

Построение оптимальных алгоритмов массовых вычислений в задачах цифровой фильтрации
за авторством: Анисимов, А.В., та інші
Опубліковано: (2008)

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

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

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

О сложности одной задачи оптимизации упаковок
за авторством: Трофимчук, А.Н., та інші
Опубліковано: (2016)

Применение комбинированного метода выпуклого программирования в задачах финансовой математики
за авторством: Бойко, В.В., та інші
Опубліковано: (2008)

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

О работах киевской школы теоретической криптографии
за авторством: Савчук, М.Н.
Опубліковано: (2010)

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

О криптографических свойствах нового национального стандарта шифрования Украины
за авторством: Алексейчук, А.Н., та інші
Опубліковано: (2016)

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

О двух типах нелинейных автоматов над конечным кольцом
за авторством: Скобелев, В.В.
Опубліковано: (2009)

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

О некоторых множествах автоматов над конечным кольцом
за авторством: Скобелев, В.Г.
Опубліковано: (2011)

О численном моделировании и оптимизации однонаправленных волновых процеcсов в неоднородных средах
за авторством: Гладкий, А.В., та інші
Опубліковано: (2010)

Верификация UCM-спецификаций распределенных систем с использованием раскрашенных сетей Петри
за авторством: Визовитин, Н.В., та інші
Опубліковано: (2015)

О радиусе устойчивости векторной задачи целочисленного линейного программирования в случае регулярности нормы в критериальном пространстве
за авторством: Емеличев, В.А., та інші
Опубліковано: (2010)

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

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

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

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