M. Pawan Kumar













An Example Fractional Solution for Cliques

Clique of Regions
Fractional Solution


The above example shows a clique of six regions r1,...,r6 where r4 = r1 ∪ r2, r5 = r1 ∪ r3 and r6 = r2 ∪ r3. 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 ith and jth 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.