Cover Image

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

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

Saved in:

Bibliographic Details
Published in:	Кибернетика и системный анализ
Date:	2012
ISSN:	0023-1274
Main Author:	Михайлюк, В.А.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Subjects:	Кибернетика
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/84037
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Реоптимизация задачи о максимальном k-покрытии: порог отношения аппроксимации / В.А. Михайлюк // Кибернетика и системный анализ. — 2012. — Т. 48, № 2. — С. 97-104. — Бібліогр.: 14 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

Similar Items

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задачи оптимизации на графах с интервальными параметрами
by: Перепелица, В.А., et al.
Published: (2009)

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

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

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

Мера неопределенности задачи Беллмана–Джонсона с интервальными длительностями
by: Сотсков, Ю.Н., et al.
Published: (2012)

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

Применение ускоренного моделирования к оценке количества некоторых k-мерных подпространств над конечным полем
by: Масол, В.И., et al.
Published: (2010)

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

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

Порог и лестница в «Мертвых душах» Гоголя
by: Кривонос, В.
Published: (2007)

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

Метод решения k-SAT-задачи сведением ее к задаче о покрытии
by: Листровой, С.В., et al.
Published: (2015)

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

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

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

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

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

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

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

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

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

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

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

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