Murota K. Matrices and Matroids for Systems Analysis
Подождите немного. Документ загружается.
312 5. Polynomial Matrix and Valuated Matroid
Proof. We prove the claim for (B
+
, B
+
) by adapting Fujishige’s proof tech-
nique developed in Fujishige [79] for the independent assignment problem
(see also Fujishige [82, Lemma 5.4]).
First note that the exchangeability graph G(B
+
, B
+
)forM
+
has a per-
fect matching Q ∩ A
+
under the correspondence in Remark 5.2.43. Take
a maximum-weight perfect matching M
= {(u
i
,v
i
) | i =1, ···,m} in
G(B
+
, B
+
), where m = |B
+
\ B
+
|, as well as the potential function 6p in
Lemma 5.2.32(1). Then M
is a subset of
A
∗
= {(u, v) | u ∈ B
+
\ B
+
,v ∈ B
+
\ B
+
,ω
+
(B
+
,u,v) − 6p(u)+6p(v)=0}.
Put Q
=(Q \ A
+
) ∪ M
, regarding M
as a subset of A
+
. Then Q
is a
disjoint union of cycles in
˜
G
M
with its length
γ(Q
)=γ(Q)+[γ(M
) − γ(Q ∩ A
+
)]
being negative, since −γ(M
) is equal to the maximum weight of a perfect
matching in G(B
+
, B
+
)andQ ∩ A
+
is a perfect matching in G(B
+
, B
+
).
The minimality of Q (with respect to the number of arcs) implies that Q
itself is a negative cycle having the smallest number of arcs.
Suppose, to the contrary, that (B
+
, B
+
) does not satisfy the unique-
max condition. Since (u
i
,v
i
) ∈ A
∗
for i =1, ···,m, it follows from Lemma
5.2.32(2) that there are distinct indices i
k
(k =1, ···,q; q ≥ 2) such that
(u
i
k
,v
i
k+1
) ∈ A
∗
for k =1, ···,q, where i
q+1
= i
1
.Thatis,
ω
+
(B
+
,u
i
k
,v
i
k+1
)=6p(u
i
k
) − 6p(v
i
k+1
)(k =1, ···,q).
On the other hand we have
ω
+
(B
+
,u
i
k
,v
i
k
)=6p(u
i
k
) − 6p(v
i
k
)(k =1, ···,q).
It then follows that
q
k=1
ω
+
(B
+
,u
i
k
,v
i
k+1
)=
q
k=1
ω
+
(B
+
,u
i
k
,v
i
k
)
=
q
k=1
[6p(u
i
k
) − 6p(v
i
k
)]
i.e.,
q
k=1
γ(u
i
k
,v
i
k+1
)=
q
k=1
γ(u
i
k
,v
i
k
). (5.57)
For k =1, ···,q,letP
(v
i
k+1
,u
i
k
) denote the path on Q
from v
i
k+1
to
u
i
k
, and let Q
k
be the directed cycle formed by arc (u
i
k
,v
i
k+1
) and path
P
(v
i
k+1
,u
i
k
). Obviously,
γ(Q
k
)=γ(u
i
k
,v
i
k+1
)+γ(P
(v
i
k+1
,u
i
k
)) (k =1, ···,q). (5.58)
A simple but crucial observation here is that
5.2 Valuated Matroid 313
q
k=1
P
(v
i
k+1
,u
i
k
)
∪{(u
i
k
,v
i
k
) | k =1, ···,q} = q
· Q
for some q
with 1 ≤ q
<q, where the union denotes the multiset union, and
this expression means that each element of Q
appears q
times on the left
hand side. Hence by adding (5.58) over k =1, ···,q we obtain
q
k=1
γ(Q
k
)=
q
k=1
γ(u
i
k
,v
i
k+1
)+
q
k=1
γ(P
(v
i
k+1
,u
i
k
))
=
'
q
k=1
γ(u
i
k
,v
i
k+1
) −
q
k=1
γ(u
i
k
,v
i
k
)
(
+ q
· γ(Q
)
= q
· γ(Q
) < 0,
where the last equality is due to (5.57). This implies that γ(Q
k
) < 0for
some k, while Q
k
has a smaller number of arcs than Q
. This contradicts the
minimality of Q
. Therefore (B
+
, B
+
) satisfies the unique-max condition.
Similarly for (B
−
, B
−
).
Lemma 5.2.45. For a negative cycle Q in
˜
G
M
having the smallest number
of arcs,
M =(M \{a ∈ M | a ∈ Q ∩ M
◦
}) ∪ (Q ∩ A
◦
)
is an independent assignment with Ω(
M) ≥ Ω(M) − γ
M
(Q)(>Ω(M )).
Proof. Note that
B
+
= ∂
+
M and B
−
= ∂
−
M for B
+
and B
−
defined in
(5.55) and (5.56), and recall the notation B
+
= ∂
+
M and B
−
= ∂
−
M.By
Lemma 5.2.44 and the unique-max lemma (Lemma 5.2.35) we have
ω
+
(B
+
)=ω
+
(B
+
)+6ω
+
(B
+
, B
+
) ≥ ω
+
(B
+
) − γ(Q ∩ A
+
),
ω
−
(B
−
)=ω
−
(B
−
)+6ω
−
(B
−
, B
−
) ≥ ω
−
(B
−
) − γ(Q ∩ A
−
).
Also we have
w(
M)=w(M) − γ(Q ∩ (A
◦
∪ M
◦
)).
Addition of these inequalities yields Ω(
M) ≥ Ω(M) − γ(Q).
The above lemma shows “(OPT) ⇒ (NNC)”.
(NNC) ⇒ (POT): By Theorem 2.2.35(1), (NNC) implies the existence of
a function p : V
+
∪ V
−
→ R such that
γ(a)+p(∂
+
a) − p(∂
−
a) ≥ 0(a ∈
˜
A). (5.59)
This condition for a ∈ A
◦
∪M
◦
is equivalent to the condition (i) in Theorem
5.2.39(1). For a =(u, v) ∈ A
+
it means
314 5. Polynomial Matrix and Valuated Matroid
ω
+
(B
+
,u,v) − p(u)+p(v) ≤ 0.
Namely, ω
+
[p
+
](B
+
,u,v) ≤ 0 for all (u, v) with B
+
+u−v ∈B
+
. This in turn
implies the condition (ii) by Theorem 5.2.7. Similarly, the above condition
for a ∈ A
−
implies the condition (iii). Thus “(NNC) ⇒ (POT)” has been
shown.
(POT) ⇒ (OPT): For any independent assignment M and any function
p : V
+
∪ V
−
→ R we see
Ω(M )=ω
+
(∂
+
M)+ω
−
(∂
−
M)+w(M)
=
'
ω
+
(∂
+
M)+
a∈M
p(∂
+
a)
(
+
'
ω
−
(∂
−
M) −
a∈M
p(∂
−
a)
(
+
a∈M
[w(a) − p(∂
+
a)+p(∂
−
a)]
= ω
+
[p
+
](∂
+
M)+ω
−
[−p
−
](∂
−
M)+
a∈M
w
p
(a), (5.60)
where w
p
(a)=w(a) − p(∂
+
a)+p(∂
−
a).
Suppose M and p satisfy (i)–(iii) of Theorem 5.2.39(1), and take an arbi-
trary independent assignment M
. Then we have
Ω(M
)=ω
+
[p
+
](∂
+
M
)+ω
−
[−p
−
](∂
−
M
)+
a∈M
w
p
(a)
≤ ω
+
[p
+
](∂
+
M)+ω
−
[−p
−
](∂
−
M)
= Ω(M). (5.61)
This shows that M is optimal, establishing “(POT) ⇒ (OPT)”. Thus we have
shown the equivalence of the three conditions (OPT), (NNC), and (POT).
For the statement (2) of Theorem 5.2.39, the expression (5.60), valid for
any M and p, implies that LHS ≤ RHS, whereas Theorem 5.2.39(1) shows
that the equality is attained. The integrality asserted in the statement (3)
of Theorem 5.2.39 can be imposed in (5.59). Finally for the statement (4) of
Theorem 5.2.39 we note in the inequality (5.61) that Ω(M
)=Ω(M )ifand
only if ω
+
[p
+
](∂
+
M
)=ω
+
[p
+
](∂
+
M), ω
−
[−p
−
](∂
−
M
)=ω
−
[−p
−
](∂
−
M),
and w
p
(a)=0fora ∈ M
.
We have completed the proofs of Theorem 5.2.39 and Theorem 5.2.42.
Extension to VIAP(k). The optimality criteria for VIAP(k) introduced
in §5.2.9 are stated explicitly for later references.
Theorem 5.2.46.
(1) Afeasiblesolution(M, B
+
,B
−
) for VIAP(k) is optimal if and only
if there exists a “potential” function p : V
+
∪ V
−
→ R such that
(i) w(a) − p(∂
+
a)+p(∂
−
a)
≤ 0(a ∈ A)
=0(a ∈ M)
5.2 Valuated Matroid 315
(ii) B
+
is a maximum-weight base of M
+
with respect to ω
+
[p
+
],
(iii) B
−
is a maximum-weight base of M
−
with respect to ω
−
[−p
−
],
(iv) p(u) ≥ p(v)(u ∈ V
+
,v∈ B
+
\ ∂
+
M),
(v) p(u) ≤ p(v)(u ∈ V
−
,v∈ B
−
\ ∂
−
M).
(2) If ω
+
, ω
−
,andw are all integer-valued, the potential p in (1) can be
taken to be integer-valued.
(3) Let p be a potential that satisfies (i)–(v) in (1) for some (optimal)
(M
0
,B
+
0
,B
−
0
).Then(M, B
+
,B
−
) is optimal if and only if it satisfies (i)–
(v).
Proof. Formulate VIAP(k) as the VIAP on G
k
=(V
+
k
,V
−
k
; A
k
) as defined in
§5.2.9, and apply Theorem 5.2.39.
For a negative-cycle criterion of optimality we need to introduce an aux-
iliary graph
˜
G
(M,B
+
,B
−
)
=(
˜
V,
˜
A) associated with (M, B
+
,B
−
), which is a
slight modification of the one used for VIAP. The vertex set
˜
V of
˜
G
(M,B
+
,B
−
)
is given by
˜
V = V
+
∪ V
−
∪{s
+
,s
−
},
where s
+
and s
−
are new vertices referred to as the source vertex and the
sink vertex respectively. The arc set
˜
A consists of eight disjoint parts:
˜
A =(A
◦
∪ M
◦
) ∪ (A
+
∪ F
+
∪ S
+
) ∪ (A
−
∪ F
−
∪ S
−
),
where
A
◦
= {a | a ∈ A} (copy of A),
M
◦
= {a | a ∈ M } (a: reorientation of a),
A
+
= {(u, v) | u ∈ B
+
,v ∈ V
+
\ B
+
,B
+
− u + v ∈B
+
},
F
+
= {(u, s
+
) | u ∈ V
+
}, (5.62)
S
+
= {(s
+
,v) | v ∈ B
+
\ ∂
+
M},
A
−
= {(v, u) | u ∈ B
−
,v ∈ V
−
\ B
−
,B
−
− u + v ∈B
−
},
F
−
= {(s
−
,u) | u ∈ V
−
},
S
−
= {(v, s
−
) | v ∈ B
−
\ ∂
−
M}.
The arc length γ(a)=γ
(M,B
+
,B
−
)
(a)(a ∈
˜
A) is defined by
γ(a)=
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
−w(a)(a ∈ A
◦
)
w(
a)(a =(u, v) ∈ M
◦
, a =(v, u) ∈ M)
−ω
+
(B
+
,u,v)(a =(u, v) ∈ A
+
)
−ω
−
(B
−
,u,v)(a =(v, u) ∈ A
−
)
0(a ∈ F
+
∪ S
+
∪ F
−
∪ S
−
).
(5.63)
Theorem 5.2.47. Afeasiblesolution(M,B
+
,B
−
) for VIAP(k) is optimal
if and only if there exists in
˜
G
(M,B
+
,B
−
)
no negative cycle with respect to the
arc length γ
(M,B
+
,B
−
)
.
316 5. Polynomial Matrix and Valuated Matroid
Proof. Formulate VIAP(k) as the VIAP on G
k
=(V
+
k
,V
−
k
; A
k
) as defined in
§5.2.9, and apply Theorem 5.2.42.
Remark 5.2.48. The definitions of F
+
and F
−
could be replaced by
F
+
= {(u, s
+
) | u ∈ ∂
+
M ∪ (V
+
\ B
+
)},
F
−
= {(s
−
,u) | u ∈ ∂
−
M ∪ (V
−
\ B
−
)}
without affecting the above theorem. The present definition is more conve-
nient for the algorithm to be developed later. 2
Remark 5.2.49. When k = r
+
= r
−
, the auxiliary graph
˜
G
(M,B
+
,B
−
)
con-
tains the auxiliary graph
˜
G
M
as a subgraph. 2
5.2.11 Application to Triple Matrix Product
Before going on to algorithms for the valuated independent assignment prob-
lem, we digress here into a possible application of the duality result in The-
orem 5.2.39 to linear algebra. The connection to a triple matrix product ex-
plained here conforms with the historical development of the independent
assignment problem explained in Remark 2.3.37.
The following fact is noted by Murota [233].
Theorem 5.2.50. Assume that a matrix product P (s)=Q
1
(s)T (s)Q
2
(s)
is nonsingular, where Q
1
(s) (resp., Q
2
(s))isak × m (resp., n × k)ra-
tional matrix over a field K,andT (s) is an m × n rational matrix over
an extension field F (⊇ K) such that the set of the coefficients is alge-
braically independent over K. Then there exist k × k nonsingular rational
matrices S
1
(s), S
2
(s) and diagonal matrices diag (s; p) = diag (s
p
1
, ···,s
p
m
),
diag (s; q) = diag (s
q
1
, ···,s
q
n
) with p ∈ Z
m
and q ∈ Z
n
such that
deg
s
det P = deg
s
det S
1
+ deg
s
det S
2
and the matrices
¯
Q
1
(s)=S
1
(s)
−1
Q
1
(s) diag (s; p),
¯
T (s) = diag (s; −p) T (s) diag (s; −q),
¯
Q
2
(s) = diag (s; q) Q
2
(s) S
2
(s)
−1
are all proper. Note that S
1
(s)
−1
P (s)S
2
(s)
−1
=
¯
Q
1
(s)
¯
T (s)
¯
Q
2
(s).
Proof. Firstly, by the Cauchy–Binet formula (Proposition 2.1.6), we have
det P =
|I|=|J|=k
±det Q
1
[R, I] · det T [I,J] · det Q
2
[J, C],
5.2 Valuated Matroid 317
where R =Row(Q
1
)andC = Col(Q
2
). There is no numerical cancellation
in the summation above by virtue of the assumed algebraic independence of
the coefficients in T (s), and hence
deg
s
det P = max
|I|=|J|=k
{deg
s
det Q
1
[R, I]+deg
s
det T [I,J]+deg
s
det Q
2
[J, C]}.
Next, consider a valuated independent assignment problem defined as
follows. The vertex sets V
+
and V
−
are the row set and the column set of
T (s), respectively, and the arc set A = {(i, j) | T
ij
(s) =0}. The valuated
matroids M
+
=(V
+
,ω
+
)andM
−
=(V
−
,ω
−
) attached to V
+
and V
−
respectively are those defined by Q
1
(s) and the transpose of Q
2
(s)asin
(5.15), i.e.,
ω
+
(I) = deg
s
det Q
1
[R, I],ω
−
(J) = deg
s
det Q
2
[J, C]
and the weight w
ij
of an edge (i, j) ∈ A is defined by w
ij
= deg
s
T
ij
(s).
Note that the maximum value of
(i,j)∈M
w
ij
over all matchings M with
I = ∂
+
M and J = ∂
−
M is equal to deg
s
det T [I,J].
Then we see from the above expression of deg
s
det P that deg
s
det P is
equal to the maximum value of the objective function Ω(M) of (5.52) over all
independent assignment M.LetM be an optimal independent assignment
and put I = ∂
+
M and J = ∂
−
M. Let ˆp : V
+
∪ V
−
→ Z be the potential
in Theorem 5.2.39, and define p ∈ Z
m
and q ∈ Z
n
by p
i
=ˆp
i
for i ∈
V
+
and q
j
= −ˆp
j
for j ∈ V
−
. Define S
1
= Q
1
[R, I] diag (s; p
I
)andS
2
=
diag (s; q
J
) Q
2
[J, C], where p
I
=(p
i
| i ∈ I) ∈ Z
I
is the restriction of p to I
and similarly for q
J
∈ Z
J
.
The conditions (i), (ii), and (iii) in Theorem 5.2.39(1), coupled with (5.24),
imply the properness of
¯
T (s),
¯
Q
1
(s), and
¯
Q
2
(s), respectively.
Remark 5.2.51. The close relationship between the triple matrix product
and the independent assignment problem through the Cauchy–Binet formula
was first observed by Tomizawa–Iri [317, 318]. To be more precise, the rank
of P = Q
1
TQ
2
was expressed in Tomizawa–Iri [317] as the maximum size
of an independent matching (cf. Remark 2.3.37), whereas the degree of the
determinant of P (s)=Q
1
T (s)Q
2
with constant matrices Q
i
(i =1, 2) was
represented in Tomizawa–Iri [318] as the optimal value of an independent
assignment. Theorem 5.2.50 gives an extension of this idea to the more general
case with polynomial/rational matrices Q
i
(s)(i =1, 2) by means of valuated
matroids with an additional explicit statement concerning the transformation
into proper matrices. 2
5.2.12 Cycle-canceling Algorithms
This section describes a primal-type cycle-canceling algorithm for the valu-
ated independent assignment problem, due to Murota [225]. The algorithm
runs in strongly polynomial time with oracles for the valuations ω
±
. Another
algorithm of primal-dual augmenting type will be given in §5.2.13.
318 5. Polynomial Matrix and Valuated Matroid
Algorithms. Our cycle-canceling algorithm is based on the negative-cycle
criterion (Theorem 5.2.42). It can be polished up to a strongly polynomial
algorithm using the minimum-ratio-cycle strategy.
In Theorem 5.2.42 we have shown a negative-cycle criterion for the opti-
mality with reference to an auxiliary graph
˜
G
M
=(
˜
V,
˜
A) with
˜
V = V
+
∪V
−
and
˜
A = A
◦
∪ M
◦
∪ A
+
∪ A
−
, where
A
◦
= {a | a ∈ A} (copy of A),
M
◦
= {a | a ∈ M } (a: reorientation of a),
A
+
= {(u, v) | u ∈ B
+
,v ∈ V
+
\ B
+
,B
+
− u + v ∈B
+
},
A
−
= {(v, u) | u ∈ B
−
,v ∈ V
−
\ B
−
,B
−
− u + v ∈B
−
}.
Here B
+
= ∂
+
M and B
−
= ∂
−
M. The arc length γ
M
(a)(a ∈
˜
A) is defined
by
γ
M
(a)=
⎧
⎪
⎪
⎨
⎪
⎪
⎩
−w(a)(a ∈ A
◦
)
w(
a)(a =(u, v) ∈ M
◦
, a =(v, u) ∈ M)
−ω
+
(B
+
,u,v)(a =(u, v) ∈ A
+
)
−ω
−
(B
−
,u,v)(a =(v, u) ∈ A
−
)
where ω
+
(B
+
,u,v)andω
−
(B
−
,u,v) are as in (5.21).
Theorem 5.2.42 as well as its proof suggests the following algorithm for
solving the valuated independent assignment problem.
Cycle-canceling algorithm
Starting from an arbitrary independent assignment M, repeat (i)–(ii)
below while there exists a negative cycle in
˜
G
M
:
(i) Find a negative cycle Q having the smallest number of arcs in
the auxiliary graph
˜
G
M
(with respect to the arc length γ
M
).
(ii) Modify the current independent matching along the cycle Q by
M =(M \{a ∈ M | a ∈ Q ∩ M
◦
}) ∪ (Q ∩ A
◦
).
The validity of this procedure follows from Theorem 5.2.42 and Lemma 5.2.45.
Remark 5.2.52. This is a straightforward extension of the primal algorithm
of Fujishige [79] for the ordinary independent assignment problem, which
extends the classical idea of Klein [160] and which is further extended later
by Fujishige [80] and by Zimmermann [352] for the submodular flow problem
(see also Fujishige [82] and the references therein). 2
The above algorithm assumes an initial independent assignment M,which
can be found by the algorithm for the independent matching problem treated
in §2.3.5. For each M the graph
˜
G
M
can be constructed with r
+
(|V
+
|−r
+
)
evaluations of ω
+
and r
−
(|V
−
|−r
−
) evaluations of ω
−
, where r
+
and r
−
are
the ranks of M
+
and M
−
respectively (we have r
+
= r
−
for a feasible prob-
lem). When the valuated matroids are associated with polynomial/rational
5.2 Valuated Matroid 319
matrices as in Examples 5.2.3 and 5.2.10, ω
±
(·, ·, ·) can be determined by
pivoting operations on the matrices if arithmetic operations on rational func-
tions can be performed.
A negative cycle having the smallest number of arcs in (i) can be found
easily by a variant of the standard shortest-path algorithm. It should however
be worth noting that the minimality of the number of arcs is not really
necessary, and in fact this observation adds more flexibility to the algorithm,
as we will see soon. Recalling the notation
B
+
=(B
+
\{∂
+
a | a ∈ Q ∩ A
+
}) ∪{∂
−
a | a ∈ Q ∩ A
+
}, (5.64)
B
−
=(B
−
\{∂
−
a | a ∈ Q ∩ A
−
}) ∪{∂
+
a | a ∈ Q ∩ A
−
}, (5.65)
we call a cycle Q in
˜
G
M
admissible if both (B
+
, B
+
) and (B
−
, B
−
) satisfy
the unique-max condition in M
+
and M
−
respectively. The admissibility of
Q guarantees (by the unique-max lemma) that the modified matching
M
remains an independent assignment.
In the proof of Lemma 5.2.44 it has been shown that if a negative cycle
Q is not admissible, a family of cycles, denoted Q
k
(k =1, ···,q) there, is
naturally defined and that at least one of its members is a negative cycle. We
call each Q
k
an induced cycle. The above observations lead to the following
refinements of Lemma 5.2.44 and Lemma 5.2.45.
Lemma 5.2.53. Let Q be a negative cycle in
˜
G
M
. Then either Q is ad-
missible or else it induces a negative cycle having a smaller number of arcs
than Q. In particular, a negative cycle having the smallest number of arcs is
admissible. 2
Lemma 5.2.54. For an admissible cycle Q in
˜
G
M
, M is an independent
assignment with Ω(
M) ≥ Ω(M) − γ
M
(Q). 2
The algorithm finds the optimal independent assignment in a finite num-
ber of steps since there exist a finite number of independent assignments in
the given graph and the objective function value Ω(M) increases monotoni-
cally; we have seen
Ω(
M) ≥ Ω(M) − γ
M
(Q)(>Ω(M )). (5.66)
However, the number of iterations of the loop (i)–(ii) is not bounded by a
polynomial in the problem size, as is also the case with the original form of
the primal algorithm for the ordinary independent assignment problem.
Zimmermann [353] has shown (for the submodular flow problem) that a
judicious choice of a negative cycle renders the number of iterations bounded
by r
+
(= r
−
). The idea is to introduce an auxiliary weight function α on
˜
A
andtoselectacycleQ of minimum ratio γ
M
(Q)/α(Q) (satisfying some extra
condition). In what follows we shall show that this idea carries over to our
320 5. Polynomial Matrix and Valuated Matroid
problem, making the number of iterations of the loop (i)–(ii) of our algorithm
bounded by r
+
(= r
−
).
We maintain a subset M
•
of
˜
A, called the active arc set, and define
α :
˜
A →{0, 1} by
α(a)=
1(a ∈ M
•
)
0(a ∈
˜
A \ M
•
).
An arc is said to be active if it belongs to M
•
. A cycle Q (⊆
˜
A) is called a
minimum-ratio cycle with respect to (γ
M
,α)ifγ
M
(Q)/α(Q) takes the mini-
mum value among all cycles with α(Q) > 0.
Cycle-canceling algorithm with minimum-ratio cycle
Starting from an arbitrary independent assignment M and active
arc set defined by M
•
= M
◦
(≡{a | a ∈ M }), repeat (i)–(iii) below
while there exists a negative cycle in
˜
G
M
:
(i) Find an admissible minimum-ratio cycle Q in the auxiliary graph
˜
G
M
(with respect to (γ
M
,α)).
(ii) Modify the current active arc set by
M
•
= M
•
\ (Q ∩ M
◦
)
and the function α accordingly.
(iii) Modify the current independent matching along the cycle Q by
M =(M \{a ∈ M | a ∈ Q ∩ M
◦
}) ∪ (Q ∩ A
◦
).
The following properties are maintained throughout the computation:
• Any negative cycle in
˜
G
M
contains an active arc (cf. Lemma 5.2.60).
• M is an independent assignment (i.e., ∂
+
M ∈B
+
, ∂
−
M ∈B
−
).
Because of the first property, the minimum-ratio cycle in (i) is well-defined,
as long as
˜
G
M
contains a negative cycle. In (ii), on the other hand, the active
arc set M
•
decreases monotonically, at least by one element in each iteration.
This implies the termination of the algorithm in at most r
+
(= r
−
) iterations,
whereas the obtained matching M is an optimal independent assignment by
the second property and Theorem 5.2.42.
An admissible minimum-ratio cycle can be found in a polynomial time in
the problem size as follows. By an algorithm of Megiddo [193] a minimum-
ratio cycle Q can be generated in O(|
˜
V |
2
|
˜
A|log |
˜
V |) time. We can test for the
admissibility of Q on the basis of Lemma 5.2.32 by means of an algorithm for
the weighted bipartite matching problem. This takes O(|
˜
V |
3
) or less time. In
case Q is not admissible, it induces at least one minimum-ratio cycle having
a smaller number of arcs than Q, as will be shown later in Lemma 5.2.57.
We pick up one of the induced minimum-ratio cycles, and repeat the above
procedure. After repeating not more than |
˜
V | times we are guaranteed to
obtain an admissible minimum-ratio cycle.
5.2 Valuated Matroid 321
Summarizing the above arguments we have the following theorem due to
Murota [225].
Theorem 5.2.55. The cycle-canceling algorithm with minimum-ratio cycle
selection is a strongly polynomial time algorithm (modulo a polynomial num-
ber of evaluations of ω
±
). 2
Other algorithms for VIAP based on the negative-cycle criterion can be
found in Murota [225] and Shigeno [296].
Validity of the Minimum-ratio Cycle Algorithm. We shall show the
validity of the cycle-canceling algorithm using the minimum-ratio cycle se-
lection. Basically we follow the arguments in Goldberg–Tarjan [96], Zimmer-
mann [353] while establishing two lemmas (Lemma 5.2.57 and Lemma 5.2.59)
specific to our problem. We abbreviate γ
M
to γ for notational simplicity.
For ≥ 0 an independent assignment M is said to be -optimal (with
respect to α) if there exists a function p :
˜
V → R such that
γ
p
(a) ≡ γ(a)+p(∂
+
a) − p(∂
−
a) ≥−α(a)(a ∈
˜
A). (5.67)
Noting (5.67) is equivalent to saying that the modified arc length ˆγ(a)=
γ(a)+α(a) admits a function p such that
ˆγ(a)+p(∂
+
a) − p(∂
−
a) ≥ 0(a ∈
˜
A),
we see that the existence of p with (5.67) is also equivalent to
γ(Q) ≥−α(Q)(Q : negative cycle).
This implies obviously that α(Q) > 0 for any negative cycle Q;thatis:
any negative cycle in
˜
G
M
contains an active arc. (5.68)
Conversely suppose (5.68) is true and
there exists a negative cycle. (5.69)
Then the “minimum cycle ratio”
μ = min
γ(Q)
α(Q)
| Q : cycle with α(Q) > 0
7
(5.70)
is a well-defined negative number, and M is -optimal for = −μ>0. Hence
we have the following statement.
Lemma 5.2.56. Condition (5.68) is satisfied if and only if M is -optimal
for some ≥ 0.