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?
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ 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. $\endgroup$– TpecatteCommented Oct 9, 2013 at 12:18
-
3$\begingroup$ 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. $\endgroup$– RaphaelCommented Oct 11, 2013 at 7:28
-
$\begingroup$ 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. $\endgroup$– vznCommented Oct 17, 2013 at 15:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
In general when you want to bound the approximation ratio of an algorithm you look for an easy lower bound on the optimal value. The most straightforward is often the LP relaxation of a (suitably chosen) ILP formulation of the problem. Sometimes other things are used, for TSP for example you can also use the weight of a MST (the optimal tour minus one edge is a tree, so it can't weigh less than the MST).
For particular instances you can of course still use the thing you use in your proofs, i.e. you can solve the LP and compare your heuristic solution to the LP value. If you have more CPU time on your hands you can also start a branch-and-bound process to solve the ILP. Even if you don't solve the ILP completely, you get better lower bounds from LP duality.
-
$\begingroup$ Can you please explain or give me a link to read about. What is LP, ILP,MST $\endgroup$ Commented Oct 17, 2013 at 12:49
-
1$\begingroup$ I edited my answer to include wikipedia links. $\endgroup$– adrianNCommented Oct 17, 2013 at 15:01