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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 22: Строка 22:
  
  
−
[[Category:Нерешенные задачи]]
+
[[Category:На проверку]]
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
 +
 +
<!--[[Файл:Celyh-max-cut.pdf|Celyh-max-cut]]-->
 +
<latex>
 +
Решение (Целых Влада, 974 группа):
 +
Дан неориентированный граф $G = (V,E)$ с весами $w_e>0$. Необходимо найти
 +
разрез $(S,T)$ с максимальным весом $R(S,T)$.
 +
Детерминированный 2-приближенный полиномиальный алгоритм: сначала $S = \{v_1\}, T = \{v_2\}$.
 +
Каждую следующую вершину относим ко множеству, сумма весов ребер до вершин которого минимальна, т.е.
 +
если $\sum_{e\in E(S,v)} w_e > \sum_{e\in E(T,v)} w_e$, то $T=T\cup \{v\}$, иначе $S=S\cup \{v\}$.
 +
 +
На каждой итерации работы алгоритма выполняется:
 +
\begin{align}
 +
\sum_{e\in E(S,T)} w_e \geq \sum_{e\in E(S,S)} w_e + \sum_{e\in E(T,T)} w_e \label{feat}
 +
\end{align}
 +
в силу того, что в начале работы алгоритма это верно ($w_{(v_1,v_2)} \geq 0$), а
 +
добавление вершины, например, ко множеству $S$ приводит к:
 +
\begin{align*}
 +
&\sum_{e\in E(S\cup \{v\},T)} w_e = \sum_{e\in E(S,T)} w_e + \sum_{e\in E(v,T)} w_e \geq
 +
\sum_{e\in E(S,S)} w_e + \sum_{e\in E(T,T)} w_e +\\
 +
  &+ \sum_{e\in E(v,S)} w_e = \sum_{e\in E(S\cup v,S \cup v)} w_e + \sum_{e\in E(T,T)} w_e,
 +
\end{align*}
 +
что и утверждалось.
 +
 +
Из~(\ref{feat}) следует, что
 +
$$
 +
2 \cdot \sum_{e\in E(S,T)} w_e \geq \sum_{e\in E(S,T)} w_e + \sum_{e\in E(S,S)} w_e + \sum_{e\in E(T,T)} w_e = \sum_{e\in E} w_e \geq OPT,
 +
$$
 +
где OPT-оптимальное решение задачи. Таким образом, предложенный алгоритм является 2-приближенным.
 +
</latex>

Версия 08:29, 12 декабря 2014

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

Источник — «https://discopal.ispras.ru/index.php?title=MAX-CUT:_вероятностное_округление/Задачи/Детерминированный_2-приближенный_алгоритм_для_задачи_MAX-CUT&oldid=3240»