An improved assignment lower bound for the Euclidean traveling salesman problem (Q1058993)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3902426
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | An improved assignment lower bound for the Euclidean traveling salesman problem |
scientific article; zbMATH DE number 3902426 |
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
0.9058828353881836
0 references
0.8607026934623718
0 references
0.8140373826026917
0 references
0.8065424561500549
0 references
