is there a general method to evaluate the optimality of an optimization algorithm, for example an algorithm solving an otherwise NP-hard or NP-complete problem?
The only method I came up so far is comparing the results of the algorithm against already known optimal solutions.
If not, are there specific methods for some special problems?
EDIT To clarify: By optimality I mean how close the result is to an optimal solutions result.
It depends on the kind of problem.
If there is a polynomial-time approximation scheme (PTAS) for the problem (e.g. Euclidian TSP), then you can get a solution that's arbitrarily close to the optimal solution in polynomial time. That means, for every e > 0, there is a polynomial time algorithm that will find an approximate solution to your problem, that is guaranteed to be within (1+e) of the optimal solution. In that case, you would just compare the runtime/memory complexity for two algorithms for the same values of e. If one algorithm can make the same "optimality guarantees" than the other, but at a lower running time/memory cost, then it's probably the better algorithm.
If the problem is APX, but not PTAS, i.e. if there are polynomial time approximation algorithms that are guaranteed to produce solutions that are within a constant factor of the optimal solution, then you can compare that constant factor. The one with the lower factor will produce the better solutions (but often at the cost of higher running time/memory costs)
If the problem is in neither of those classes, then I think the best you can do is to compare their solutions for a set of random problems, or for problems with known optimal solutions.
I don't think there's a general way of doing it, but there are certainly methods of doing so.
Take, for example, the problem SET-COVER. For those who don't know the problem is as follows:
Given a set of elements B={1,2,...,m} and a number of subsets S_1, S_2, ..., S_n whose union is B. You are trying to find the minimum number of these subsets such that the union is still B. A real-world typical example of this problem is where you're given a collection of neighborhoods and you are trying to find the optimal places to place schools such that each neighborhood is serviced less than some distance d away from the nearest school. In this case, B is the set of neighborhoods and S_x consists of all sets within d of town x.
You prove that this problem is NP-COMPLETE. However there is a simple greedy solution where you repeatedly pick the set S_i with the largest number of uncovered elements. And you can prove that this algorithm does well.
If the optimal algorithm consists of k sets, the greedy algorithm will consist of no more than k ln(n) sets where ln is the natural logarithm.
The problem of determining whether a program has 'optimality performance' A or 'optimality performance' B for just about any definition of 'optimality performance' is undecidable in general (proof below). This implies that there is no single method that can always tell you how optimal an algorithm is.
There are however methods that are often applied when analyzing approximation algorithms. Often, approximation algorithms are evaluated by their guarantees on how far its solution is from the optimal solution. I'll give an example problem and approximation, which I will prove using the 'lower bound' method, which is a very commonly used method to prove ratios.
The problem in question is the 'Truck Loading' problem: we have a lot of identical trucks (as many as we like), each capable of carrying a load weighing at most T. We have n objects we wish to load in these trucks for transport. Every object i has a weight w_i, where w_i <= T (so there are no items that can't fit on a truck even by themselves). Items cannot be divided into parts. We'd like to fill up trucks so that we need as few trucks as possible. This problem is NP-complete.
There is a very easy approximation algorithm for this problem. We simply start loading a truck with items, until the truck is so full that the next item won't fit. We then take another truck and load this truck with this item that didn't fit on the previous truck. We don't load any more items on this truck: instead, we take a new truck, we fill it with lots of items again until it no longer fits, put that last item on its own truck again and so forth.
This algorithm is a so-called 2-approximation for the problem: it uses at most twice as many trucks as the optimal solution would need. The 'at most' is crucial: we might be lucky and find the optimal solution, but at least we won't do too bad.
To prove this, we first define a lower bound on the optimal number of trucks we need. For this, imagine that we are allowed to cut items into parts: we could then easily fill every truck but the last one completely. The number of trucks we'd need if we did that is a lower bound for the number of trucks we need for the original question: in the 'best' case the optimal solution always fills every truck completely, in which case the number of trucks is equal, but if the optimal solutions leaves trucks unfilled, then it can only need more trucks.
Now we look at our approximation algorithm. Note that in every step, we (partially) fill up two trucks. Also note that by how the algorithm works, the items in the first truck and the item in the second truck together cannot fit in the first truck, so their sum is at least T. This means that every step, we load at least a full truck worth of items on two trucks. Now compare this to our lower bound: in that case, we load a full truck worth of items on one truck. In other words, our approximation algorithm computes (in linear time) a solution that looks very much like our lower bound 'solution', but uses two trucks instead of one. Hence, we use at most twice as many trucks as the optimal algorithm, because we use at most twice as many trucks as our lower bound on the optimal algorithm.
This algorithm gives a constant-factor approximation: it is at most 2 times as bad as the optimal solution. Some examples of other measures: at most C more than the optimal solution (additive error, quite uncommon), at most c log n times as bad as the optimal solution, at most c n times as bad as the optimal solution, at most c 2 ^ (d n) times as bad as the optimal solution (very bad; for instance, general TSP only admits algorithms with this kind of guarantees).
Of course, if you want to be sure that the factor you prove is the best factor you can prove, you should try to find instances in which the solution your algorithm gives is indeed as bad as it possibly can be.
Also note that we sometimes use approximation algorithms on problems that are not NP-hard.
I learned this (among a lot more) in the approximation algorithms course at my university.
Undecidability proof: let P be a problem and A and B be approximation algorithms for P where A and B do not have the same 'optimality' for some sensible definition of 'optimality', and where the running time of A and B is both omega(1) (strictly slower than constant time, ie, they become slower for larger instances) and where A and B both always halt.
Let D be a program that claims that it can compute the following: given some program C computing an approximation for P, decide whether it is as good as A or as good as B for sufficiently large inputs (you can therefore use this to categorize programs according to their optimality).
We can then use D to solve the halting problem. Let E be a program and F be an input for this program. We will use D to decide whether E will halt on input F.
We design a program G that does the following: given an input S for problem P, it runs E on F and A on S in parallel: it executes E for a while, then A, then E again and so forth. If E halts on F, it stops running A and instead runs B on S and returns B's result. If A halts before E halts, it returns A's result.
Using D on G now decides whether E halts on F: if E halts on F, then for sufficiently large inputs S, E halts on F before A halts on S (because the time it takes E to halt does not depend on the size of the input, unlike A). D therefore reports that G has the optimality characteristics of B. If E doesn't halt on F, D will report that G has the optimality characteristics of A.
