An improved assignment lower bound for the Euclidean traveling salesman problem (Q1058993): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
| (One intermediate revision by one other user not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The Traveling-Salesman Problem / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3720323 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A man-machine approach toward solving the traveling salesman problem / rank | |||
Normal rank | |||
Latest revision as of 17:52, 14 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An improved assignment lower bound for the Euclidean traveling salesman problem |
scientific article |
Statements
An improved assignment lower bound for the Euclidean traveling salesman problem (English)
0 references
1985
0 references
A simple transformation of the distance matrix for the Euclidean traveling salesman problem is presented that produces a tighter lower bound on the length of the optimal tour than has previously been attainable using the assignment relaxation. The improved lower bound is obtained by exploiting geometric properties of the problem to produce fewer and larger subtours on the first solution of the assignment problem. This research should improve the performance of assignment based exact procedures and may lead to improved heuristics for the traveling salesman problem.
0 references
flow algorithms
0 references
transformation of the distance matrix
0 references
Euclidean traveling salesman
0 references
lower bound
0 references
improved heuristics
0 references
0 references
