В этой задаче мне дан граф G = (V,E), цель состоит в том, чтобы найти раскраску вершин графа тремя возможными цветами, которые максимизируют функцию качества.
q(c) = количество ребер, концы которых окрашены по-разному.
Дайте вероятностное приближение 3/2 и покажите, что алгоритм возвращает ошибку (что означает худшее приближение) с вероятностью не более d^-k для каждого натурального числа k и для фиксированного d>= 1.
Теперь я дал следующий алгоритм: я окрашиваю каждую вершину случайным образом, это означает, что ожидаемая вероятность того, что ребро будет иметь разные цветные ребра, составляет 2/3, что делает его приближением 3/2.
Тем не менее, я понятия не имею, как показать, что он возвращает отказ с вероятностью не более d^-k.
Мог бы помочь, спасибо!
