MAX-SAT: вероятностное округление/Задачи/eupce-6-3-b — различия между версиями

Версия 16:13, 18 мая 2023

Бонусная задача

• Дан n-вершинный неориентированный граф G=(V, E)

Рассмотрим следующий метод генерации независимого множества.

Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда никакой ни один сосед j вершины i не предшествует i в перестановке σ.

Предложите вероятностный алгоритм для поиска σ для которого можно показать, что ожидаемый размер

где означает степень вершины i.

Докажите, что в G существует независимое множество размера как минимум