Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm stuck at one point of this paper that I'm reading atm. Just can't understand why they're doing this:

The general topic is performance of algorithms, that will not always compute the exact solution of the problem. So I have a pretty special linear problem and I want to make some conclusions on the "effectiveness" of a given algorithm. First of all what exactly is meant by effectiveness - is it the time or is it the error of the computed value relative to the real optimal value ?

In detail: It's about vehicle minimization in deliveries and such. First the author gives a lower bound on the number of vehicles that you might need to make all the deliveries for a given set of customers, then he proceedes with an upper bound (which is the number of customers). After that he takes the ratio of these two values, meaning:

"upper bound / lower bound" := n/c

The conclusion is: "The algorithm will achieve at worst a factor n/c result"

What does that mean ... ?

Thanks in advance :)

share|improve this question
    
Do you have a link to the paper? –  Michael Chen Jan 24 '12 at 21:49
    
    
You are absolutely right as it seems - I'm just too dumb / tired to figure it out myself... >_> Thank you very much :) –  tesseract Jan 24 '12 at 22:01
    
Oh cool, you're reading an OR paper. I'm doing some work in that field now. Good luck with it! –  Michael Chen Jan 24 '12 at 22:49

1 Answer 1

up vote 0 down vote accepted

If I read this correctly, the author is saying that there is a range of solutions that the algorithm can put out. The lower bound is the best possible since the problem is minimization. Then the farthest you can get from the optimal solution is at the other end, the upper bound.

Therefore, at worst you are higher bound / lower bound away from the best solution.

For example, if my lower bound is 2 and my upper bound is 8, you are at worst a factor of $8/2=4$ away from the optimal solution.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.