An O(N log N) Expected Time Merge Heuristic for the Planar ETSP

Simple item page
dc.contributor.authorChadha, Rituen
dc.contributor.authorAllison, Donald C. S.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:51Zen
dc.date.available2013-06-19T14:36:51Zen
dc.date.issued1988en
dc.description.abstractWe discuss a new heuristic for solving the Euclidean Traveling Salesman Problem (ETSP). This heuristic is a convex hull-based method and makes use of the Delaunay triangulation of the set of cities to compute a tour for the given set of cities. We conjecture that the expected running time for this algorithm is O(N log N), implying that a new and faster ETSP heuristic is now available.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00000101/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000101/01/TR-88-16.pdfen
dc.identifier.trnumberTR-88-16en
dc.identifier.urihttp://hdl.handle.net/10919/19385en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleAn O(N log N) Expected Time Merge Heuristic for the Planar ETSPen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR-88-16.pdf
Size:
604.24 KB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science Technical Reports