Timeline for How can you bound the error of an approximation without knowing the optimal solution?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2013 at 19:53 | review | First posts | |||
| Nov 8, 2013 at 4:19 | |||||
| Oct 22, 2013 at 12:20 | vote | accept | Ilya Gazman | ||
| Oct 17, 2013 at 15:05 | comment | added | vzn | 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. | |
| Oct 11, 2013 at 8:38 | answer | added | adrianN | timeline score: 8 | |
| Oct 11, 2013 at 7:28 | history | edited | Raphael | CC BY-SA 3.0 |
edited tags
|
| Oct 11, 2013 at 7:28 | comment | added | Raphael | 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. | |
| Oct 9, 2013 at 12:21 | history | tweeted | twitter.com/#!/StackCompSci/status/387915605606944768 | ||
| Oct 9, 2013 at 12:18 | comment | added | Tpecatte | 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. | |
| Oct 9, 2013 at 12:03 | history | asked | Ilya Gazman | CC BY-SA 3.0 |