The name is absent

Lemma 3.2 Let σ be a node in the graph Γ. Then

(1) deg(σ) = 1 when σ = { v };

(2) deg(σ) is either zero or one when σ is a completely labeled simplex;

(3) deg(σ) is either one or two in all other cases.

Lemma 3.2 implies that the sequence of adjacent simpIices of varying dimension
starting from the O-dimensional simplex { v } generated by the algorithm may lead
to a completely labeled simplex, or may terminate with an integral point in P, or
may go to infinity. We will prove that the latter case can be excluded.

As norm we use the Euclidean norm in Rⁿ. We now define an open ball of radius
7 centered at v by

B(7) = { X ∈ Rⁿ I ||æ — _υ∣∣ ≤ 7 }.

We have the following lemma.

Lemma 3.3 For any proper subset T of N, there is no Т-complete (t — 1)-
simplex in A(T)∖B(^f) provided that is chosen to be a sufficiently large number.

Proof: It is a straightforward consequence of the fact that when operating in Rⁿ,
the algorithm always moves into the direction in which for some j ∈ .V. the function
ajx — b_j is strictly decreasing because of q(if^γ ai < 0 for all i ∈ .∖.              □

Now it is easy to obtain the following result by noticing that the number of nodes
in the graph Γ is finite and the algorithm can never return to a node previously
visited.

Lemma 3.4 Let an п-simplex P be given in standard form. Then the algorithm
will terminate with either an integral point in P or a completely labeled simplex of
type II, within a finite number of steps.

<<   8   9   10   11   12   13   14   >>

More intriguing information