M. Pawan Kumar 
HOME

An Example Fractional Solution for Cliques
The above example shows a clique of six regions r_{1},...,r_{6} where r_{4} = r_{1} ∪ r_{2}, r_{5} = r_{1} ∪ r_{3} and r_{6} = r_{2} ∪ r_{3}. Each region can either be selected (label 1) or not selected (label 0). The regions are shown as circles while the labels are shown as trellises on top of the regions (bottom branch of the trellis is label 0; top branch is label 1). All unary potentials (shown next to the corresponding branch of the trellis) are 0. The pairwise potential θ_{rr'}(i,j) (shown next to the connection between the i^{th} and j^{th} branches of regions r and r') is not 0 only when i = 1 and j = 1. Such pairwise potentials introduce frustration into the problem of minimizing the energy corresponding to this clique. Thus, the optimal solution of the linear programming relaxation is fractional. Note that the fractional solution also satisfies all cycle inequalities. Thus, their addition to the linear program will not result in a tight relaxation.
