MAX-CUT: вероятностное округление/Задачи/0.5-приближенный вероятностный для MAX-CUT — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | ===== Задача «0.5-приближенный вероятностный для MAX-CUT» ===== | + | |
| + | ===== Задача «0.5-приближенный вероятностный для MAX-CUT» ===== | ||
<latex> | <latex> | ||
| − | Для задачи о поиске максимального разреза в простом, | + | |
| + | Для задачи о поиске максимального разреза в простом, невзвешенном графе можно применить простую стратегию: | ||
каждую вершину равновероятно ($p=1/2$) приписать к~множеству $T$ или $S$. | каждую вершину равновероятно ($p=1/2$) приписать к~множеству $T$ или $S$. | ||
| + | Докажите, что этот вероятностный алгоритм является $0.5$-приближенным. | ||
| + | </latex> | ||
| − | + | [[Категория:На проверку]] | |
| − | + | ===Стенина Мария, группа 974=== | |
| − | + | <latex> | |
| − | < | + | Обозначим максимально возможный размер разреза $R^*$, а размер разреза, полученный рандомизированным алгоритмом, $R$. Найдем математическое ожидание $\mathbb{E} R$. Каждое ребро попадает в разрез с вероятностью 0.5, потому что при описанном способе отнесения вершин к одной из частей графа вероятность того, что обе вершины, инцидентные ребру, окажутся по разные стороны разреза, равна 0.5. Поэтому ожидание числа ребер в разрезе |
| + | $$ | ||
| + | \mathbb{E} R = \frac{1}{2} |E| \geq \frac{1}{2} R^*, | ||
| + | $$ | ||
| + | что и требовалось доказать. | ||
| + | </latex> | ||
Версия 09:01, 17 октября 2014
Задача «0.5-приближенный вероятностный для MAX-CUT»
Стенина Мария, группа 974