Set TerminologyDate: 07/07/97 at 12:18:05 From: Bob Howell 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. Thank you, Bob Howell Date: 07/07/97 at 18:48:10 From: Doctor Daniel Subject: Re: Some more math terminology help, please Hi Bob, So you're working with approximation algorithms, huh? That's actually what I do as well, so I'll try to be a little specific to your problem domain. Actually, the definition you've given is only one of a few that are common for the description of the performance of an approximation algorithm. I'll explain the definition you give and then follow up with the slightly more common definition. You can find a copy of the definition I use in Chapter 37 of _Introduction to Algorithms_ by Corman, Leiserson and Rivest (which, if you're working on algorithm design or implementation, should probably be on your shelf.) Anyhow, inf means "infimum," or "greatest lower bound." This is slightly different from minimum in that the greatest lower bound is defined as: x is the infimum of the set S [in symbols, x = inf (S)] iff: a) x is less than or equal to all elements of S b) there is no other number larger than x which is less than or equal to all elements of S. Basically, (a) means that x is a lower bound of S, and (b) means that x is greater than all other lower bounds of S. This differs from min (S) in that min (S) has to be a member of S. Suppose that S = {2, 1.1, 1.01, 1.001, 1.0001, 1.00001, ...}. This set has no smallest member, no minimum. However, it's trivial to show that 1 is its infimum; clearly all elements are greater than or equal to 1, and if we thought that something greater than 1 was a lower bound, it'd be easy to show some member of S which is less than it. So that's the difference between inf and min. It's worth noting that every set has an inf (assuming minus infinity is okay), and that the two concepts are the same for finite sets. A couple of last terminology bits: glb is another way of writing inf (sort for "greatest lower bound"), and then there are two other concepts that are similar for upper bounds, sup and lub, which are short for "supremum" and "least upper bound." So what are we talking about here with these approximation algorithms? Basically, the absolute performance ratio is not a way to combine min/max problems. It's actually more important. The idea is one of the central ones in algorithm design: an algorithm is as weak as its _WORST_ example. Suppose that we have an approximation algorithm A, and that, over the set of all possible instances for the problem, it returns values of RA of: 1.2, 1.5, 1.4, 1.2, 1.5, 1.2, 1.01, 600000, 1.3, ... Given just this small set of data, it's clear that we can't claim that we should expect "good" performance from the algorithm. There's that bad case where the algorithm returned a result that was 600,000 times off the correct one; either in a minimization problem the answer was six hundred thousand times too big, or in a maximization problem the answer was way too small. So the performance ratio is at least 600,000. Actually, that definition you gave me is a pretty bad one. Let's consider what it means. It means we want the greatest lower bound of the set of all numbers r greater than 1 such that RA (I) is less than r for all instances I of the problem. What does it mean that r is one of these numbers? If you look at it, r has to be an upper bound for the set of values of RA(I) for all instances I of the problem. So we want the greatest lower bound of a set of upper bounds on the performance ratio. We know that RA (I) >= 1 always, so if RA(I) <= r, then r >= 1 always, so the qualification that r has to be greater than or equal to one is irrelevant. So really, we're looking for the GLB of a bunch of upper bounds of a set. Turns out, that's the lub. So: RA = sup {RA(I) for all instances I. I'm afraid I may have put way too much into the last paragraphs. Perhaps if you look at an example, it may be clearer: Suppose that there is a finite set of possible instances, with these performance ratios: 1.3, 1.5, 1.6, 45, 1.2, 5.6 Then the set of all r's that satisfy the definition you gave me would be any number greater than or equal to 45, since RA(I) <= r for all instances I, and RA(I) = 45 for some instance. So the inf of this set would be 45, which is also the sup of the set of performance ratios I gave. Here's an infinite example: Suppose that the performance ratios look like this: 1.3, 1.76, 1.9, 1.6, 1.99, 1.8, 1.999, 1.45, 1.99999999999, 1.2, 1.99999999999999999999999, ... (with them arbitrarily close to 2) Then clearly the infimum of the set of upper bounds to this set is 2, so this approximation algorithm would have a performance guarantee of 2. But that's also the supremum of the set of performance ratios. I hope that begins to make things a little clearer, at least for the definition of performance ratio that you gave. However, that's not a fair definition of the performance ratio for some approximation algorithms. Suppose that I can give you an approximation algorithm with this guarantee: "On an instance of size n (namely, that can be encoded in n bits), I guarantee that the answer returned will be no more than log log n times the minimum." That's a pretty good guarantee; log log n is usually quite small; certainly less than 10. However, according to this definition, since log log n does grow to infinity as n grows to infinity, this algorithm will have an RA value of infinity. How distressing! The solution to this is to allow the performance guarantee to be a function of the size of the input. (Incidentally, if this is getting too heavy, feel free to not read the rest of this message. On the other hand, _I'm_ currently designing such an approximation algorithm, so why shouldn't you? Anyhow, be sure to read the summary at the end of this message.) The problem with the definition of RA above is that it doesn't depend on the length of the input. So here's an alternative definition of a possible time bound: We say that an approximation algorithm for the problem has a ratio bound of rho (n) ("is a rho-approximation algorithm" is more standard) if, for all instances I of size n, RA(I) <= rho (n). (paraphrase from p. 964 of _Intro to Algorithms_) Note that this notation is much less precise; since log (n) is less than n, it means that a log(n)-approximation algorithm is also an n-approximation algorithm. But it does take into account my worry from above; my algorithm is now identifiable as a log log (n)-approximation algorithm, and people will feel much safer using it than they would have if it were advertised as having an absolute performance ratio of infinity! So, now that I've thrown pages and pages at you, let's summarize: INF means greatest lower bound. It's the largest number which is less than or equal to all elements of a set S. It differs from the minimum in that it does not have to be an element of S, but is the same for finite sets. It can be written as glb. SUP is the opposite of inf; it means least upper bound, and can also be written lub. The definition of absolute performance ratio you gave talks about the worst possible performance of the algorithm. We need to be sure that we're never claiming that the algorithm does better than it might on some anomalous instance of the problem. Another definition of the performance ratio of an algorithm, which is far more standard (but a little newer), compares the algorithm's performance ratio on all instances of size n to a function of n; the algorithm is a rho-approximation if, for all instances of size n, RA(n) <= rho (n). This notation is a little less precise, but is much more useful for some problems when the best known approximation algorithm would have an absolute performance ratio of infinity, by the other definition. I'd welcome further questions about these definitions, or about what you're reading, if you have them. Be advised that I don't think there are that many math doctors who do theoretical computer science, so it may take a while before you get a reply. (I hesitate to point out that you're also a little beyond what most of our K-12 questions are like, as well.) Good luck! -Doctor Daniel, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/