understanding proof for greedy algorithm for linear optimization on base polyhedra

87 Views Asked by At

I am following the proof in the Fujishige book (Proof is in the image).

I did not understand the thrid step (from the bottom). On what basis author set $w_p(y(A_p) - x(A_p))$ as zero. It is true that $A_p$ is the ground set. But since $y$ and $x$ are not equal, how the term cancels out ?

Proof From the Book

1

There are 1 best solutions below

0
On

By the definition of the base polyhedron, we have $z(A_p) = f(A_p)$ for any base $z \in B(f)$. As $x(A_p) = f(A_p)$ by (3.65), the third-last step follows.