# How can you bound the error of an approximation without knowing the optimal solution?

I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length it is supposed to be?

• The solutions are AT MOST 0.031% higher than the optimal tour is. Without finding the optimal tour, one can still find lower bound on it and on the approximation algorithm, which hence allow to "compare" approximate solutions with optimal solution. – Tpecatte Oct 9 '13 at 12:18
• You should really, really pick up a book about complexity theory and/or how to solve NP-hard problems. You have little hope of actually solving P?=NP in your lifetime and convincing anybody that you did if you keep pushing out proposals/questions that prove that you have not understood undergraduate concepts. Of course, we can help you get to this understanding. – Raphael Oct 11 '13 at 7:28
• it would be helpful if you cite the person stating that limit [TO, same]. afaik, there is no such P-time limit known in general. there are other approximation limits expressed in functions of the parameters of the problem eg points, etc. – vzn Oct 17 '13 at 15:05