Re: Euclidean TSP and Java

On Sat, 30 Aug 2008 15:02:01 -0700, Tim Smith <reply_in_group@xxxxxxxxxxxxxxxx> wrote:

[...]
It is known that for any N > 0, there is a polynomial time algorithm
that gets within a factor of 1+1/N of optimal for Euclidean TSP.

Is there also a known relationship between the actual polynomial time cost and any given N? Or is it simply that it can be proven that some algorithm exists?

Just curious.

.

Relevant Pages

  • Re: Why isnt NP simply "not polynomial"?
    ... Why can't NP be defined as the class of decision problems ... It is certainly possible to define a class Not-P (I'll use a different ... there is no *known* polynomial time algorithm. ...
    (comp.theory)
  • Re: Distance normalized TSP algorithm
    ... have not seen it applied to TSP, but I suspect that is mainly because it ... more challenging than that, but perhaps a bit less challenging than ... finding a polynomial time algorithm for an NP-complete problem. ...
    (comp.lang.java.programmer)
  • Re: Aspiring highest-order programmer
    ... >> active knowledge into dead secrets in such a way that one can never, ... the moment someone comes up with a polynomial time ... > polynomial time algorithm to solve the problem which makes the problem ... Doesn't this fail to answer the question as to the practicality of the ...
    (comp.programming)
  • hi guys...need insight into this interesting algorithm..Repost
    ... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
    (sci.math)
  • Interesting algorithm...need insights..
    ... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
    (sci.logic)