1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.