Cover Image

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

Для реоптимизации задачи о минимальном вершинном покрытии k-равномерного гиперграфа при добавлении h вершин (h = O(log n), n – общее число вершин) и некоторого числа гиперребер приводится полиномиальный (2–1/k) – приближенный алгоритм. При выполнении уникальной игровой гипотезы (UGC) аппроксимационн...

Full description

Saved in:

Bibliographic Details
Published in:	Компьютерная математика
Date:	2012
Main Author:	Михайлюк, В.А.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Subjects:	Теория и методы оптимизации
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/84700
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. — № 1. — С. 158-166. — Бібліогр.: 9 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

Similar Items

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

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

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

Применение "бесполезных" ходов при решении задачи о покрытии
by: Шило, П.В.
Published: (2014)

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

О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада
by: Парасюк, И.Н., et al.
Published: (2009)

О численном решении задачи стохастического оптимального управления дивидендной политикой страховой компании
by: Норкин, Б.В.
Published: (2014)

Кратчайший k-вершинный путь
by: Стецюк, П.И., et al.
Published: (2015)

Декомпозиция для решения двухуровневой задачи
by: Горбачук, В.М., et al.
Published: (2011)

Подходы к решению задачи раскраски графа
by: Шило, В.П.
Published: (2009)

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

Двойственная квадратичная оценка для линейной задачи дополнительности
by: Березовский, О.А., et al.
Published: (2017)

Метод решения задачи размещения в анизотропной области
by: Чуб, И.А., et al.
Published: (2011)

Алгоритм точного решения задачи построения помехозащищенного кода максимального объема для Z-канала
by: Шило, В.П., et al.
Published: (2017)

Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа
by: Градинар, И.П.
Published: (2010)

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

Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений
by: Листровой, С.В., et al.
Published: (2015)

Решение Н-методом задачи оптимизации маршрутов транспортных средств с временными окнами
by: Гуляницкий, Л.Ф., et al.
Published: (2012)

Реоптимізація 2-критеріальної задачі про узагальнену виконуваність
by: Михайлюк, В.О., et al.
Published: (2018)

О сходимости rµ(α)-алгоритма
by: Стецюк, П.И., et al.
Published: (2015)

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

Моделирование свертывания протеина в пространстве
by: Гуляницкий, Л.Ф., et al.
Published: (2010)

Адаптивная выигрышная стратегия для проблемы двух конвертов
by: Шило, В.П., et al.
Published: (2010)

Алгоритми розв'язання задачі сепарабельного квадратичного програмування
by: Стецюк, П.І., et al.
Published: (2017)

Інтелектуалізація обчислень для задач математичного моделювання складних процесів і об’єктів
by: Сидорук, В.А., et al.
Published: (2019)

Алгоритми синтезу класифікаторів у задачах розпізнавання об’єктів засобами лінійних і нелінійних оптимальних перетворень простору ознак
by: Гавриленко, А.С.
Published: (2012)

Коническая регуляризация в задачах квадратичной оптимизации
by: Лаптин, Ю.П.
Published: (2016)

Выпуклые продолжения для класса квадратичных задач на перестановочных матрицах
by: Пичугина, О.С., et al.
Published: (2016)

Вартості досконалої інформації та стохастичного рішення
by: Горбачук, В.М., et al.
Published: (2017)

Разработка алгоритма синтеза систем для решения задач классификации сигналов
by: Гавриленко, А.С.
Published: (2010)

Применение оптимального алгоритма синтеза линейных систем классификации в обработке звуковых сигналов
by: Гавриленко, А.С.
Published: (2013)

Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації
by: Семенов, В.В.
Published: (2015)

Структурні та стохастичні властивості алгоритму лексикографічного пошуку розв’язку задачі дискретної оптимізації
by: Чупов, С.В.
Published: (2016)

Асимптотики ограниченных оптимальных управлений для векторных сингулярно возмущенных параболических периодических задач в критическом случае
by: Капустян, В.Е., et al.
Published: (2009)

Некоторые применения кластеризации критериального пространства для задач выбора
by: Кондрук, Н.Э., et al.
Published: (2009)

Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках
by: Парасюк, И.Н., et al.
Published: (2009)

Квадратичні задачі лексикографічної оптимізації: властивості та розв’язання
by: Ломага, М.М., et al.
Published: (2013)

Приближение функции f(x,y) суммами вида φ0(x)ψ0(y)+…+ φN(x)ψN(y)
by: Литвин, О.Н., et al.
Published: (2011)

Соленоидальные управления в коэффициентах нелинейных эллиптических краевых задач
by: Капустян, В.Е., et al.
Published: (2010)

Разработка и исследование эффективности метаэвристических алгоритмов решения задач планирования работы независимых машин
by: Туринский, В.В.
Published: (2015)