Subset-sum approximation algorithm running time

Question

in 35.5 of CLRS i have read about algorithm to find sum as large as possible, but not larger than $t.$

Essential part of this algorithm is trimming. On every step you delete all numbers which close one to another, but one to represent them all. Good explanation of the algorithm.

At page 7 from provided link or at page 1133 of ClSR 3rd edition you can find such a statement: $z'/z>1+\epsilon/2n.$ I think $z'$ and $z$ is numbers of elements before and after trimming. But i can't understand how they got such estimation. For example at first step trimming don't actually trim any element. We can devise example of sequence and epsilon to have no trimmed elements even at second step.

Can somebody, please, explain how they got such an estimation? Thanks.

Answer 1

Both $z$ and $z'$ belong to the same trimmed list, after trimming. The point is that after trimming, two adjacent elements are at a multiplicative distance of at least 1ドル+\epsilon/(2n),ドル by construction. This is why the trimmed lists are small, and so the running time is reasonable. If there is no trimming then there is no problem – the original list already satisfies this condition.

Here is a concrete example. Suppose we want our elements to be at multiplicative distance at least 2ドル,ドル and suppose that the original list is 1,2,3,4,5,6,7,8ドル$. After trimming we are left with 1,2,4,8ドル,ドル and any two adjacent elements are at multiplicative distance at least 2ドル$ (in this case, exactly 2ドル$). Had we started with, say, 1,4,9,16ドル,ドル no trimming would be necessary, but still adjacent elements are at multiplicative distance at least 2ドル$.