Consider the problem of finding the Max-Cut in a weighted graph It is known to be NP-complete to decide if the maximum cut is bigger than some parameter . It’s NP-hard to even approximate the Max-Cut to an approximate ratio of (unless ) If we pick the cut randomly, that is if we decide randomly […]
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
A Neighbourhood Of Infinity 