Problem

Show how the optimal alpha-beta swap step can be found by running min-cut on an appropriately constructed graph. More precisely:

a. Define a set of binary variables t₁, . . . , t_n, such that the value of the t_i's defines an alpha-beta-swap transformation on the x_i's.

b. Define an energy function E' over the T variables such that E'(t) = E(x').

c. Show that the energy function E' is sub modular if the original energy function E is a semimetric.