The algorithm always terminates .
In each iteration of the loop the price of some set in S is increased enough to make one more element from T tight .
The algorithm always terminates because in each iteration of the loop the price of some set in S is increased enough to make one more element from T tight .