0
$\begingroup$

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 :)

  • 0
    Oh cool, you're reading an OR paper. I'm doing some work in that field now. Good luck with it!2012-01-24

1 Answers 1

0

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.