
```
Case 1: a
         2 ≥
            (a+b)
                2
                 
              2. Then F(v∗) − F(vˆ) ≤ bn2(1 − a). For a given value of a, this is maximized when b is

as large as possible. For Case 1 to hold, the largest possible value of b is given by a
                                                                                       2 =
                                                                                           (a+b)
                                                                                                2
                                                                                                 
                                                                                              2, which gives

b = a(
      √2 − 1). Therefore F(v∗) − F(vˆ) ≤
                                           n
                                            2
                                             (
                                              √2−1)
                                               4 <
                                                       n
                                                        2
                                                         
                                                        8
                                                          , i.e. F(vˆ) ≥
                                                                       8
                                                                       9
                                                                        F(v∗).

```

Case 2: a 2 ≤
(a+b)
2 2**. This holds if** b ≥ (
√2 − 1)a. Since a + b ≤ **1, this is possible only if** a ≤ 1/
√**2. Now**
F (v
∗)−F (vˆ)
n2 ≤ a 2 + b(1 − a) − (a + b)
2/2 = a 2−4ab+2b−b 2 2.

For a given a, this expression is quadratic in b **with a negative second derivative. This is maximized (by**
differentiating) for b = 1 − 2a. Since b ≤ a, this value is possible only if a ≥ 1/**3. Similarly, for case 2 to hold** with this value of b**, we must have** a ≤
√2 − 1. Substituting this value of b**, the difference in scores is** 5a 2−4a+1 2.

Since this is quadratic with a positive second derivative, it is maximized when a **has either the minimum or**
maximum possible value. For a = 1/3 this value is 1/**9, while for** a =
√2 − **1, it is 10** − 7
√**2. In both cases, it is**
less than 1/8.

If a ≤ 1/3 the maximum is achieved when b = a**. In this case, the score difference is at most (**a − 2a 2**) which**
is maximized for a = 1/4, where the value is 1/**8. (This is the worst case).**
For √2 − 1 < a ≤ 1/
√2, the maximum will occur for b = (√2 − 1)a. Substituting this value for b**, the score**
difference is (√2 − 1)(a − a 2), which is maximized for a = 1/**2, where its value is (**√2 − 1)/4 < 1/8.

We believe that the bound for general q is 4q 4q+1 . This bound is not tight as for q **= 1 we have already shown**
that the 45 bound can be tightened to 13 15 . With q = 2 we get a bound of 89 **which is better than** 13 15 .

## Entropy Potentials And The Α**-Pass Algorithm**

As an aside, let us explore the behavior of α**-pass on another family of additive potentials - entropy potentials.** Entropy potentials are of the form:

$$\mathbf{C}(\mathbf{v})=\lambda\sum_{v}n_{v}\log n_{v},{\mathrm{~where~}}\lambda>0$$
$$(27)$$
nv log nv, where λ > **0 (27)**
The main reason α**-pass provides a good bound for Potts potentials is that it guarantees a clique potential of** at least n 21 where n1 **is the count of the most dominant value in the optimal solution. The quadratic term**
compensates for possible sub-optimality of counts of other values. If we had a sub-quadratic term instead, say n1 log n1 for the entropy potentials, the same bound would not have held. In **fact the following theorem shows** that for entropy potentials, even though α-pass guarantees a clique potential of at least n1 log n1**, that is not**
enough to provide a good approximation ratio.

Theorem 6.8. α*-pass does not provide a bound better than* 12 for entropy potentials.

Proof. Consider a counter example where there are R = n + log n **values. Divide the values into two sets —** A
with log n values and B with n **values. The vertex potentials are as follows: the vertices are divided into log** n chunks of size n/ log n **each. If the** j th **vertex lies in the** v th **chunk, then let it have a vertex potential of log** n with value v in A and a vertex potential of log n + ǫ **with the** j th vertex in B**. Let all other vertex potentials be**
zero. Also, let λ **= 1.**
Consider the assignment which assigns the v th value in A **to the** v th chunk. Its score is 2n log n − n **log log** n.

Now consider α-pass, with α ∈ A. Initially vertex v **will be set to the** v th value in B**. The best assignment found**
by α-pass will assign every vertex to α, for a total score of roughly n + n log n. If α ∈ B**, then again the best**
assignment will assign everything to α for a total score of roughly (n **+ 1) log** n.

Thus the bound is no better than 12 as n → ∞.

Thus, α**-pass provides good approximations when the clique potential is dominated by the most dominated**
value. We now look at majority potentials, which are linear in the counts {nv}v**. Looking at Theorem 6.8,**
we expect that α**-pass will not have decent approximation guarantees for** majority**. This is indeed the case.**
We will prove in Section 6.3 that neither α-pass nor a natural modification of α**-pass enjoy good approximation** guarantees.