Solution Found!
In the MAXIMUM CUT problem we are given an undirected graph G = (V, E) with a weight
Chapter 9, Problem 9.9(choose chapter or problem)
In the MAXIMUM CUT problem we are given an undirected graph G = (V, E) with a weight w(e)on each edge, and we wish to separate the vertices into two sets S and V - S so that the total weight of the edges between the two sets is as large as possible.
For each \(S \subseteq V\) define w(S) to be the sum of all \(w_{u v}\) over all edges {u, v} such that \(|S \cap\{u, v\}|=1\). Obviously, MAX CUT is about maximizing w(S) over all subsets of V.
Consider the following local search algorithm for MAX CUT:
(a) Show that this is an approximation algorithm for MAX CUT with ratio 2.
(b) But is it a polynomial-time algorithm?
Questions & Answers
QUESTION:
In the MAXIMUM CUT problem we are given an undirected graph G = (V, E) with a weight w(e)on each edge, and we wish to separate the vertices into two sets S and V - S so that the total weight of the edges between the two sets is as large as possible.
For each \(S \subseteq V\) define w(S) to be the sum of all \(w_{u v}\) over all edges {u, v} such that \(|S \cap\{u, v\}|=1\). Obviously, MAX CUT is about maximizing w(S) over all subsets of V.
Consider the following local search algorithm for MAX CUT:
(a) Show that this is an approximation algorithm for MAX CUT with ratio 2.
(b) But is it a polynomial-time algorithm?
ANSWER:Step 1 of 3
We have Given a Local search algorithm:-
start with any 
while there is a subset 
||
set 