Euclidean TSP and Java
- From: Tim Smith <reply_in_group@xxxxxxxxxxxxxxxx>
- Date: Sat, 30 Aug 2008 15:02:01 -0700
Interesting page here on Euclidean TSP:
<http://valis.cs.uiuc.edu/~sariel/research/CG/applets/tsp/TspAlg.html>
It includes a Java applet that implements two approximation algorithms
that run in polynomial time and give performance guarantees. One runs
in O(N^2 log N) and is guaranteed to get a tour is at most twice as long
as optimal. The second is guaranteed to be at most 1.5 as long as
optimal.
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.
--
--Tim Smith
.
- Follow-Ups:
- Re: Euclidean TSP and Java
- From: Peter Duniho
- Re: Euclidean TSP and Java
- Prev by Date: Re: How to make a class an alias of another one?
- Next by Date: Re: Euclidean TSP and Java
- Previous by thread: Unexplained locking failure in Java 6.0_05
- Next by thread: Re: Euclidean TSP and Java
- Index(es):
Relevant Pages
|
