StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is called <a href="http://www.itl.nist.gov/div897/sqg/dads/HTML/euclidntrvls.html" rel="nofollow noreferrer">Euclidean Travelling Salesman</a> (in 2-dimensions) and is also NP-Complete like TSP. </p> <p>The other answers are <em>inaccurate</em> as they are doing the opposite: reducing your problem to Hamiltonian Path, while it should be the other way round, to show NP-Completeness. Sorry to say this, but it seems to be a pretty common problem on this site.</p> <p>We can say that this <em>fundamentally</em> differs from the normal TSP in the following sense:</p> <p>If P != NP,</p> <ul> <li><p>There is no <a href="http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme" rel="nofollow noreferrer">PTAS</a> for TSP (in fact also for metric TSP, where distances satisfy the triangle inequality).</p></li> <li><p>There is a PTAS for Euclidean TSP. Check out this paper by Arora by which gives an 1+1/c approximation algorithm and runtime is O(n (logn)^O(c)): <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.1363" rel="nofollow noreferrer">Polynomial time approximation schemes for Euclidean TSP and other geometric problems</a>. Notice that Euclidean TSP is a <em>special</em> case of metric TSP and yet it differs in this way.</p></li> </ul> <p>There are other algorithms which guarantee 2-approximation (using Minimum Spanning Trees) and 3/2-approximation and might be simpler. Arora's paper mentions those and you should be able to track down using the references in Arora's paper.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload