next up previous
Next: Proofsketch of Theorem 5 Up: Appendix A Previous: Proof of Theorem 3

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

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


\begin{displaymath}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}]\:\:.\end{displaymath}

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:
$\displaystyle f[A\cup B] + f[A\cap B]$ $\textstyle \leq$ $\displaystyle 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 :

\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}]} \:\:.

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.

next up previous
Next: Proofsketch of Theorem 5 Up: Appendix A Previous: Proof of Theorem 3
2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.