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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 16 промежуточных версий 2 участников)
Строка 1: Строка 1:
===== Задача «0.5-приближенный вероятностный для MAX-CUT» =====
 
 
<latex>
 
<latex>
Для задачи о поиске максимального разреза в простом, невзвешенного графе можно применить простую стратегию:
+
Для задачи о поиске максимального разреза в простом, невзвешенном графе можно применить простую стратегию:
 
каждую вершину равновероятно ($p=1/2$) приписать к~множеству $T$ или $S$.
 
каждую вершину равновероятно ($p=1/2$) приписать к~множеству $T$ или $S$.
  
 
+
Докажите, что этот вероятностный алгоритм является $0.5$-приближенным.
Докажите, что этот вероятностный алгоритм является $0.5$-приближенным.
+
 
+
 
</latex>
 
</latex>
  
[[Category:Нерешенные задачи]]
+
[[Категория:Решенные задачи]]
<!--Вообще-то, решения уже есть-->
+

Версия 15:49, 20 мая 2020