problem 4

[Jared Saia]

A couple hints for problem 4 (based on discussions in my office hours):

1) Set this up as a s-t min cut problem.  In particular, create a graph G' with a source and sink such that the min cut for G' will give an optimal segmentation of the original graph.

2) To follow hint 1, you need to change things into a minimization problem.  Here's a hint for how to do this.  Let S = the sum of all the a_i's and all the b_i's.  Then note that:

L(A,B) = S - sum_(i in B) b_i - sum_(j in A) a_i - sum_(edges i and j that have exactly one endpoint in A) p_i,j

Now note that the maximization of L(A,B) is the same as the minimization of something else.  The rest of the problem is to determine how to do this minimization.

Hope this helps. 

Jared

[Jared Saia]

There's a typo in my second hint.  See the correction below.

 

On Wed, Dec 5, 2012 at 9:21 AM, Jared Saia <sa...@cs.unm.edu> wrote:

A couple hints for problem 4 (based on discussions in my office hours):

1) Set this up as a s-t min cut problem.  In particular, create a graph G' with a source and sink such that the min cut for G' will give an optimal segmentation of the original graph.

2) To follow hint 1, you need to change things into a minimization problem.  Here's a hint for how to do this.  Let S = the sum of all the a_i's and all the b_i's.  Then note that:

L(A,B) = S - sum_(i in B) b_i - sum_(j in A) a_i - sum_(edges i and j that have exactly one endpoint in A) p_i,j

This should be:

L(A,B) = S - sum_(i in B) a_i - sum_(j in A) b_j - sum_(edges i and j that have exactly one endpoint in A) p_i,j

Thanks to Scott for pointing this out.

Jared

 

Now note that the maximization of L(A,B) is the same as the minimization of something else.  The rest of the problem is to determine how to do this minimization.

Hope this helps. 

Jared

--