Theorem: The maximum cut problem
in [Math]
|
From: Link on 8 Apr 2010 08:45 Theorem: The maximum cut problem can be approximated in polynomial time within 1.14*OPT. =1.0625*OPT
From: marty.musatov on 8 Apr 2010 04:55 > Theorem: The maximum cut problem can be > > > approximated in polynomial time within 1.14*OPT. > > > =1.0625*OPT One of Karp's original NP-complete problems. A B C D E A B C D E Input graph Heuristic solution Optimal solution A B C D E cut size = 2 cut size = 4 cut size = 5 Maximum Cut Theorem [Karp, 1972]: The minimum vertex cover problem is NP-complete. Theorem: The maximum cut problem can be solved in polynomial time for planar graphs. Theorem: The maximum cut problem can not be approximated within £ 17/16*OPT unless P=NP. Theorem: The maximum cut problem can be approximated in polynomial time within 2*OPT. Theorem: The maximum cut problem can be approximated in polynomial time within 1.14*OPT. =1.0625*OPT Maximum Cut Algorithm: 2*OPT approximation for maximum cut: Start with an arbitrary node partition If moving an arbitrary node across the partition will improve the cut, then do so Repeat until no further improvement is possible Idea: final cut must contain at least half of all edges. Þ Heuristic solution is no worse than 2*OPT. A B C D E Input graph Heuristic solution Optimal solution cut size = 2 cut size = 3 A B C D E A B C D E cut size = 5
|
Pages: 1 Prev: Distance between ellipses Next: Geometric TSP can be approximated |