Max 3 цвета алгоритм

Question

В этой задаче я дал график G = (V,E), цель состоит в том, чтобы найти раскраску вершин графа с 3-х возможных цветов, которые максимизируют функцию качества

д (с) = количество края, что их конечные точки окрашены по-разному.

Дайте probalistic 3/2 приближения, и показать, что алгоритм возвращается не в состоянии (что означает худшее приближение) с вероятностью большей d^-k для каждого натурального числа k и фиксированной d>= 1.

Теперь я дал следующий алгоритм: Я произвольно разбиваю каждую вершину, что означает, что ожидаемая вероятность того, что кромка будет иметь разные красы цвета, равна 2/3, что делает ее приближением 3/2.

Однако я не знаю, как показать, что он возвращает сбой с вероятностью не более d^-k.

Не могли бы вам помочь, спасибо!

Answer 1

Вместо того, чтобы пытаться распутать здесь квантификаторы, я просто хочу заметить, что метод условных ожиданий может быть использован для правильной проверки правильного алгоритма, реализуемого с помощью алгоритма.

Пока существует неокрашенная вершина, покрасьте ее в один из цветов, который наименее представлен среди его соседей.

Идея состоит в том, что каждый край с неокрашенной конечной точкой стоит 2/3 в ожидании независимо от того, какие другие варианты были сделаны, при условии, что мы произвольно окрасим остальную часть графика. Используя самый разнообразный выбор, мы получаем как минимум такое детерминированное значение, какое мы потеряли в рандомизированном значении.