Re: Euclidean TSP and Java

In article <op.ugpzu8jx8jd0ej@xxxxxxxxxxxxxxxxxxxx>,
"Peter Duniho" <NpOeStPeAdM@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.

According to the Wikipedia article on TSP, there is a polynomial time
that gets within 1+1/N in time O(n (log n)^O(N).

Here's the paper Wikipedia cites:

<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.6765>

That page has a download link for the paper.

--
--Tim Smith
.

Relevant Pages

  • Re: Euclidean TSP and Java
    ... 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? ...
    (comp.lang.java.programmer)
  • Euclidean TSP and Java
    ... Interesting page here on Euclidean TSP: ... It includes a Java applet that implements two approximation algorithms ... It is known that for any N> 0, there is a polynomial time algorithm ...
    (comp.lang.java.programmer)