An approximation algorithm is called a c-approximation algorithm for some constant c if it can be proven that the solution that the algorithm finds is at most c times worse than the optimal solution. Here, c is called the approximation ratio. Depending on whether the problem is a minimization or a maximization problem, this can either denote c times larger or c times smaller, respectively. For example, the vertex cover problem and traveling salesman problem with triangle inequality each have simple 2-approximation algorithms. In contrast to that it's proven that the traveling salesman problem with arbitrary edge-lengths can not be approximated with approximation ratio bounded by a constant as long as the Hamiltonian-path problem can not be solved in polynomial time.
They're like those embedded 3-d Magic Eye posters for your entire left hemisphere! If you look hard enough, you can see a sailboat, travelling the shortest route between several islands that are various fixed distances from each other.
No comments:
Post a Comment