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

Реоптимизация задачи о максимальном k-покрытии: порог отношения аппроксимации

Представлено алгоритм реоптимізації, на якому досягається відношення апроксимації 1-(1/(e+1))+ε. A reoptimization algorithm with approximation ratio 1-(1/(e+1))+ε is presented.

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

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

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

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

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

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

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

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

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

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

Двойственные оценки для задачи о максимальном К-клабе
за авторством: Березовский, О.А., та інші
Опубліковано: (2008)

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

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

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

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

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

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

О решении динамической задачи оптимального разбиения множеств с размещением центров подмножеств
за авторством: Киселева, Е.М., та інші
Опубліковано: (2014)

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

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

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

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

О максимальном расхождении между двумя эмпирическими распределениями
за авторством: Рвачева, Е. Л., та інші
Опубліковано: (1952)

Мера неопределенности задачи Беллмана–Джонсона с интервальными длительностями
за авторством: Сотсков, Ю.Н., та інші
Опубліковано: (2012)

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

Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем
за авторством: Масол, В.И., та інші
Опубліковано: (2010)

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

Порог и лестница в «Мертвых душах» Гоголя
за авторством: Кривонос, В.
Опубліковано: (2007)

Нижний температурный порог развития корневой свекловичной тли
за авторством: Федоренко, В.П.
Опубліковано: (1984)

Метод решения k-SAT-задачи сведением ее к задаче о покрытии
за авторством: Листровой, С.В., та інші
Опубліковано: (2015)

Верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем
за авторством: Кузнецов, И.Н.
Опубліковано: (2010)

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

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

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

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

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

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

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

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

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

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

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