A Novel Solution to the ATT48 Benchmark Problem

Simple item page
dc.creatorRuffa, Anthony A.
dc.date2007-10-02
dc.date.accessioned2026-07-07T08:33:33Z
dc.date.available2026-07-07T08:33:33Z
dc.descriptionA solution to the benchmark ATT48 Traveling Salesman Problem (from the TSPLIB95 library) results from isolating the set of vertices into ten open-ended zones with nine lengthwise boundaries. In each zone, a minimum-length Hamiltonian Path (HP) is found for each combination of boundary vertices, leading to an approximation for the minimum-length Hamiltonian Cycle (HC). Determination of the optimal HPs for subsequent zones has the effect of automatically filtering out non-optimal HPs from earlier zones. Although the optimal HC for ATT48 involves only two crossing edges between all zones (with one exception), adding inter-zone edges can accommodate more complex problems.
dc.identifierhttps://arxiv.org/abs/0710.0539
dc.identifierhttp://arxiv.org/abs/0710.0539
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/139170
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.titleA Novel Solution to the ATT48 Benchmark Problem
dc.typetext

Files

Collections

arXiv