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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
</latex>
 
</latex>
  
−
[[Категория:На проверку]]
+
[[Category:Решенные задачи]]
−
 
+
−
===Стенина Мария, группа 974===
+
−
 
+
−
<latex>
+
−
Обозначим максимально возможный размер разреза $R^*$, а размер разреза, полученный рандомизированным алгоритмом, $R$. Найдем математическое ожидание $\mathbb{E} R$. Каждое ребро попадает в разрез с вероятностью 0.5, потому что при описанном способе отнесения вершин к одной из частей графа вероятность того, что обе вершины, инцидентные ребру, окажутся по разные стороны разреза, равна 0.5. Поэтому ожидание числа ребер в разрезе
+
−
$$
+
−
    \mathbb{E} R = \frac{1}{2} |E| \geq \frac{1}{2} R^*,
+
−
$$
+
−
что и требовалось доказать.
+
−
</latex>
+

Версия 00:49, 11 декабря 2014

Задача «0.5-приближенный вероятностный для MAX-CUT»

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