Proof of Theorem 4

Table 3: Possible coefficients of $w((o,k,j))$. We have fixed for short $S_1=\{0, 1, ..., c-1\} \backslash (A\cup B)$, $S_2=A\backslash B$, $S_3=B\backslash A$, $S_4=A\cap B$.

		coefficient of $w((o,k,j))$ in
$k \in$	$l \in$	$f[A\cup B] + f[A\cap B]$	$f[A] + f[B]$
$S_1$	$S_1$	2	2
$S_1$	$S_2$	$e^{-\alpha} +1$	$e^{-\alpha} +1$
$S_1$	$S_3$	$e^{-\alpha} +1$	$e^{-\alpha} +1$
$S_1$	$S_4$	$2 e^{-\alpha}$	$2 e^{-\alpha}$
$S_2$	$S_1$	$e^\alpha +1$	$e^\alpha +1$
$S_2$	$S_2$	2	2
$S_2$	$S_3$	2	$e^\alpha + e^{-\alpha}$
$S_2$	$S_4$	$1 + e^{-\alpha}$	$1 + e^{-\alpha}$
$S_3$	$S_1$	$e^\alpha +1$	$e^\alpha +1$
$S_3$	$S_2$	2	$e^\alpha + e^{-\alpha}$
$S_3$	$S_3$	2	2
$S_3$	$S_4$	$1 + e^{-\alpha}$	$1 + e^{-\alpha}$
$S_4$	$S_1$	$2 e^\alpha$	$2 e^\alpha$
$S_4$	$S_2$	$1+e^\alpha$	$1+e^\alpha$
$S_4$	$S_3$	$1+e^\alpha$	$1+e^\alpha$
$S_4$	$S_4$	2	2

Define the function $f : 2^{\{0, 1, ..., c-1\}} \rightarrow I\!\!R$ such that

$$\forall A \subseteq \{0, 1, ..., c-1\}, f[A] = \sum_{o,k,j} {w((o,k,j)) q_{A}(j,k)} \:\:,$$ (21)

with

$$q_{A}(j,k) = e^{\alpha}[\hspace{-0.055cm}[j\in A \wedge k\not... ...A) \vee (j\not\in A \wedge k\not\in A) ]\hspace{-0.055cm}]\:\:.$$

Note that $f$ generalizes the three expressions of $Z$ in equations (2), (3), and (7) with adequate values for $\alpha$. Now, we check that $f$ satisfies the submodular inequality:

$$f[A\cup B] + f[A\cap B] \leq f[A] + f[B] \:\:,$$ (22)

for all subsets $A, B \subseteq \{0, 1, ..., c-1\}$. The key is to examine the coefficient of each $w((o,k,j))$, for each set $\{0, 1, ..., c-1\} \backslash (A\cup B)$, $A\backslash B$, $B\backslash A$, $A\cap B$ to which $j$ or $k$ can belong. Table 3 presents these coefficients. We get from Table 3 :

$$\begin{eqnarray*} \lefteqn{f[A\cup B] + f[A\cap B] - (f[A] + f[B]) = }\\ & & \l... ...ckslash A \wedge k \in A\backslash B) ]\hspace{-0.055cm}]} \:\:. \end{eqnarray*}$$

This last quantity is $\leq 0$ for any possible choice of $\alpha$. Therefore, minimizing $Z$ in any of its three forms of eq. (2), (3), and (7) boils down to minimizing $f$ on the submodular system $(\{0, 1, ..., c-1\},f)$ (with the adequate values of $\alpha$). This problem admits polynomial-time solving algorithms [Grötschel et al.1981,Queyranne1998]. What is much interesting is that the algorithms known are highly complicated and time consuming for the general minimization of $f$ [Queyranne1998]. However, when using the value of $\alpha$ as in eq. (4) and $Z$ as in eq. (7), the corresponding function $f$ becomes submodular symmetric ( $f[A]=f[\{0, 1, ..., c-1\} \backslash A]$). As such, more efficient (and simpler) algorithms exist to minimize $f$. For example, there exists a powerful combinatorial algorithm working in ${\cal O}(c^5)$ [Queyranne1998]. Note that this is still a very large complexity.