Search Results

By "autonomous" TSP heuristic I mean algorithms whose reported edge-set for a short Hamilton cycle is invariant under the addition of vertex weights; the terminology is borrowed from differential equa …

A simple "a posteriori" criterion is that on the optimal tour the distances to the tour-neighbors is smaller than that to any of the other vertices. Convexity alone doesn't suffice as the example of e …

Weighted $K_5$ have the unique property that their edge set can be interpreted as the disjoint union of their shortest and their longest Hamilton cycle. That makes $K_5$ attractive for designing new T …

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ …

The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is $$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace …

In the euclidean plane an common heuristic for the TSP is to start with the convex hull of the point set and then successively integrate as the next point and insertion position the combination that i …

Question: what is known about the complexity of finding the Hamilton cycle of minimum weight in graphs that resemble hypercubes with weighted edges?

Is it true that for a symmetric TSP instance in the sequence of edges generated by successively: calculating the optimal 2-factor adding cardinality constraints on the edgesets of the 2-factor's conn …

According to the TSP Gallery moats provide lower bounds for the optimal solution of TSP instances. On the webpage they are depicted as blue rings around red disks, whose radii represent maximal vertex …

In his 2009 paper General k-opt submoves for the Lin–Kernighan TSP heuristic, Helsgaun defines the local tour improvements on which the LKH heuristics are based as: with a cycle defined here: which …

G. A. Croes is the author of the first description of the 2-opt moves heuristic for improving non-optimal traveling salesman tours: Croes, G. A. “A Method for Solving Traveling-Salesman Problems.” Op …

I am currently developing TSP heuristics that aim at symmetrically reducing the original, complete and undirected graph. The overarching rationale is that the reduction is done via a sequence of regul …

Just found the answer in the 1969 paper THE TRAVELING-SALESMAN PROBLEM AND MINIMUM SPANNING TREES by Held and Karp; in which it is shown that it is not always possible to find the otimal solution to t …

Question: given a complete symmetric graph $G(V,E)$ with $n$ vertices and edges $e_{ij}$ having weight $\omega_{ij}$, does there always exists a vector of vertex potentials $(\pi_1,\,\dots,\,\pi_n)$ t …

I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in "G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling salesm …