Deadline: 2023-01-05 14:00 (2 hours ago)
Tomáš Domes — 2022-12-17 19:54 (18 days ago) — reply
*Problém MaxCut*
Vrcholy zadaného grafu chceme rozdělit do dvou disjunktních množin tak, aby mezi množinami vedlo co nejvíce hran (výstupem algoritmu je tedy informace pro každý vrchol, zda leží v levé či pravé množině). Rozhodovací verze tohoto problému je $\textsf{NP}$-úplná. Nalezněte polynomiální 2-aproximační algoritmus pro optimalizační verzi a dokažte o něm, že je skutečně polynomiální a 2-aproximační.