Paper Info
Title
Approximating TSP solution by MST based graph pyramid
Abstract
The traveling salesperson problem (TSP) is difficult to solve for input instances with large number of cities. Instead of finding the solution of an input with a large number of cities, the problem is approximated into a simpler form containing smaller number of cities, which is then solved optimally. Graph pyramid solution strategies, in a bottom-up manner using Borůvka's minimum spanning tree, convert a 2D Euclidean TSP problem with a large number of cities into successively smaller problems (graphs) with similar layout and solution, until the number of cities is small enough to seek the optimal solution. Expanding this tour solution in a top-down manner to the lower levels of the pyramid approximates the solution. The new model has an adaptive spatial structure and it simulates visual acuity and visual attention. The model solves the TSP problem sequentially, by moving attention from city to city with the same quality as humans. Graph pyramid data structures and processing strategies are a plausible model for finding near-optimal solutions for computationally hard pattern recognition problems.
Year
DOI
Venue
2007
10.1007/978-3-540-72903-7_27
GbRPR
Keywords
Field
DocType
smaller problem,smaller number,optimal solution,approximating tsp solution,euclidean tsp problem,graph pyramid solution strategy,near-optimal solution,large number,salesperson problem,tsp problem sequentially,tour solution,pattern recognition,data structure,traveling salesperson problem,top down,bottom up,spanning tree
Data structure,Graph,Mathematical optimization,Theoretical computer science,Travelling salesman problem,Visual attention,Pyramid,Euclidean geometry,Spatial structure,Mathematics,Minimum spanning tree
Conference
Volume
ISSN
Citations 
4538
0302-9743
4
PageRank 
References 
Authors
0.47
12
5
Name
Order
Citations
PageRank
Yll Haxhimusa123320.26
Walter G. Kropatsch2896152.91
Zygmunt Pizlo315822.63
Adrian Ion422221.11
Andreas Lehrbaum550.83