
## 6.2.1 Α**-Expansion**

In general graphs, a popular method that provides the approximation guarantee of 1/2 for the Potts model is the graph-cuts based α **expansion algorithm [5]. We explore the behavior of this algorithm for Potts potentials.**
In this scheme, we start with any initial assignment - for example, all **vertices are assigned the first value**
as suggested in [5]. Next, for each value α we perform an α **expansion phase where we switch the assignment of**
an optimal set of vertices to α from their current value. We repeat this until in a round over the R **values, no** vertices switch their assignment.

For graphs whose edge potentials form a metric, an optimal α **expansion move is based on the use of the**
mincut algorithm of [5] which for the case of cliques can be O(n 3).

We next show how to perform optimal α **expansion moves more efficiently for all kinds of** sum **potentials.**
An α expansion move Let v˜ be the assignment at the start of this move. For each value v 6= α **create a** sorted list Sv of vertices assigned v in v˜ in decreasing order of ψiα − ψiv**. If in an optimal move, we move** kv vertices from v to α, then it is clear that we need to pick the top kv vertices from Sv. Let ri **be the rank of a** vertex i in Sv. Our remaining task is to decide the optimal number kv to take from each Sv**. We find these using**
dynamic programming. Without log of generality assume α = R and 1, . . . , R − 1 are the R − **1 values other**
than α.

Let Dj (k) denote the best score with k vertices assigned values from 1 . . . j switched to α**. We compute**

$D_{j}(k)=\max\limits_{l\leq k,l\leq n_{j}(\tilde{\bf v})}D_{j-1}(k-l)+f_{j}(n_{j}(\tilde{\bf v})-l)$  $$+\sum\limits_{i^{\prime}:r_{i^{\prime}}\leq l}\psi_{i^{\prime}\alpha}+\sum\limits_{i^{\prime}:r_{i^{\prime}}>l}\psi_{i^{\prime}j}$$
$$-n_{\alpha}(\hat{\mathbf{v}})D_{R-1}(k)+f_{\alpha}(k+1)$$
From here we can calculate the optimal number of vertices to switch to α as argmaxk≤n−nα(v˜)DR−1(k) + fα(k +
nα(v**˜)).**
Theorem 6.6. The α-expansion algorithm provides no better approximation guarantee than 1/2 even for the special case of homogeneous Potts potential on cliques.

Proof. Consider an instance where R = k + 1, and λ = 1. Let ψu1 = 2n/k for all u and for k **disjoint groups of** n/k vertices each, let ψu,i+1 = 2n **for the vertices in the** i th **group. All other vertex potentials are zero. Consider**
the solution where every vertex is assigned value 1. This assignment is locally optimal wrt any α**-expansion** move, and its score is n 2(1 + 2/k**). However, the exact solution assigns every vertex group its value, with a score**
n 2(2 + 1/k) , thus giving a ratio of 1/**2 in the limit.**
We next present a generalization of the α**-pass algorithm that provides provably better guarantees while being**
faster than α**-expansion.**

## 6.2.2 Generalized Α**-Pass Algorithm**

In α-pass for each value α, we go over each count k and find the best vertex score with k **vertices assigned value** α. We generalize this to go over all value combinations of size no more than q**, a parameter of the algorithm** that is fixed based on the desired approximation guarantee.

For each value subset A ⊆ R′p of size no more than q, and for each count k**, maximize vertex potentials with**
k vertices assigned a value from set A. For this, sort vertices in decreasing order of maxα∈A ψiα − maxv6∈A ψvuy, assign the top k vertices their best value in A and the remaining their best value not in A**. The best solution**
over all A, k with |A| ≤ q **is the final assignment** vˆ.

The complexity of this algorithm is O(nRqlog n**). In practice, we can use heuristics to prune the number of**
value combinations. Further, we can make the following claims about the quality of its output.

## Theorem 6.7. F(Vˆ) ≥ 8 9 F(V∗).

Proof. This bound is achieved if we run the algorithm with q **= 2. Let the optimal solution have counts**
n1 ≥ n2 ≥ . . . ≥ nR and let its vertex potential be ψ∗. For simplicity let a = n1/n, b = n2/n and c = ψ∗/n2. Then F(v∗)/n2 ≤ c + a 2 + b(1 − a), F(vˆ)/n2 ≥ c + a 2 and F(vˆ)/n2 ≥ c +
(a+b)
2 2.