Table 3:
Possible coefficients of . We have fixed for short
,
,
, .
coefficient of in
2
2
2
2
2
2
2
2
2
2
Define the function
such that
(21)
with
Note that generalizes the three expressions of in equations (2), (3), and (7) with adequate values for . Now, we check that satisfies the submodular inequality:
(22)
for all subsets
. The key is to examine the coefficient of each , for each set
, , , to which or can belong. Table 3 presents these coefficients. We get from Table 3 :
This last quantity is for any possible choice of . Therefore, minimizing in any of its three forms of eq. (2), (3), and (7) boils down to minimizing on the submodular system
(with the adequate values of ). 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 [Queyranne1998]. However, when using the value of as in eq. (4) and as in eq. (7), the corresponding function becomes submodular symmetric (
). As such, more efficient (and simpler) algorithms exist to minimize . For example, there exists a powerful combinatorial algorithm working in [Queyranne1998]. Note that this is still a very large complexity.