Просмотр исходного текста страницы MAX-CUT: вероятностное округление/Задачи/Детерминированный 2-приближенный алгоритм для задачи MAX-CUT

Предложите детерминированный 2-приближенный полиномиальный алгоритм для задачи [[MAX-CUT]].

<!--
Формулировка избыточна, я сделал ссылку на постановку задачи.

===== Формулировка =====

Дан граф <m>(V, E)</m>, 
* где <m>V</m> — множество вершин,
* где <m>E</m> — множество ребер.

Через <m>|A|</m> обозначим мощность множества <m>A</m>.

Предложить алгоритм построения разреза графа, величины не менее <m>\frac{|E|}{2}</m> ребер
(так как максимальный разрез состоит не более чем из <m>|E|</m> ребер,
то данный алгоритм гарантированно даст 2-приближенное решение задачи MAX-CUT).

Разрезом называется разбиение <m>V</m> на два непересекающихся подмножества <m>S</m> и <m>T</m>.
Величиной разреза называется число ребер с концами в разных подмножествах:
<m>\{(u, v) \in E| u \in S, \; v \in T\}</m>.
 -->



<!--Вообще-то, решения уже есть-->

[[Категория:Решенные задачи]]