# Greedy Algorithm effectiveness

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

-
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

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.