zee
Posts : 115 |
 Posted 22/05/2008 01:18:16 AM | | Subject: Some more math terminology help, please
So far your help has been very valuable in understanding the math
symbols for the textbook I am studying. I am stuck again, so your help
is needed.
A(I)
Ratio RA(I) is defined as: RA(I) = ------
OPT(I)
That is, the ratio of the solution found by an approximation algorithm
A(I) to the optimal solution OPT(I) for instance I of a minimization
problem.
OPT(I)
For a maximization problem: RA(I) = ------
A(I)
So, clearly RA(I) >= 1, and the closer to 1, the better the
approximation algorithm. This I understand. Now, here is what I need
explained. What does the terminology inf{...} mean in the following
definition of the absolute performance ratio (which I assume is a way
of combining the above minimization and maximization problem ratios
into a single definition)?
The absolute performance ratio RA for an approximation algorithm A is
given by:
RA = inf{r >=1: RA(I) <=r for all instances I of the given problem.
I understand what max {...} and min{...} mean, but I have never
encountered inf{...} before.....
|
Register | 
Profile | 
Private messages | 
Search | 
Online | 
Help
| Create a free blog
Email Notification
Warn moderators
