| Affiliation: | 1.Department of Mathematics,University of the Aegean,Samos Island,Greece;2.Center for Applied Optimization, Department of Industrial and Systems Engineering,University of Florida,Gainesville,USA;3.Department of Informatics,Hellenic Open University,Patras,Greece;4.Department of Business Administration,University of Patras Computer Technology Institute and Press- “Diophantus”,Rio,Greece |
| Abstract: | In this paper, we define a new combinatorial function on the edges of complete weighted graphs. This function assigns to each edge of the graph the sum of the weights of all Hamiltonian cycles that contain the edge. Since this function involves the factorial function, whose exact calculation is intractable due to its superexponential asymptotic rate of increase, we also introduce a normalized version of the function that is efficiently computable. From this version, we derive an upper bound to the weight of the minimum weight Hamiltonian cycle of the graph based on the weights of the graph edges. Then we investigate the possible algorithmic applications of this normalized function using the Nearest Neighbor Heuristic and a smallest edge first heuristic. As evidence for its applicability, we show that the use of this function as a criterion for the selection of the next edge, improves the performance of both heuristics for approximating the minimum weight Hamiltonian cycles in Euclidean plane graphs. Moreover, our experimental results show that the use of the function is more suitable with the structure of the smallest edge first heuristic since it provides a solution closer to the best known solution of known hard TSP instances but in (O(n^3)) time. |
