Взвешенная задача MAX-k-CUT требует максимального взвешенного разреза во взвешенном неориентированном графе. Предположим теперь, что каждая вершина одна за другой жадно приписывается группе, которая может максимизировать общий вес новых разрезов. Как узнать скорость аппроксимации детерминированного алгоритма?
Как обосновать коэффициент аппроксимации этого детерминированного алгоритма (взвешенный MAX-k-Cut)
Ответы (1)
Это 1/2. Этот конкретный алгоритм можно получить, применив метод условных ожиданий к рандомизированному приближению, которое выбирает назначение каждого узла независимо и равномерно случайным образом, что дает 1/2 общего веса ребра в ожидании и, следовательно, по крайней мере 1/2 OPT.
Пример, когда отношение равно 1/2 + ε, можно получить, взяв K2,n с единичными весами ребер, добавив ребро с бесконечно минимальной стоимостью между двумя вершинами на одной стороне и заставив алгоритм учитывать их в первую очередь.
person
David Eisenstat
schedule
27.12.2020
