On patching algorithms for random asymmetric travelling salesman problems (Q1813831): Difference between revisions
From MaRDI portal
Set profile property. |
Created claim: Wikidata QID (P12): Q56324130, #quickstatements; #temporary_batch_1710346988437 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56324130 / rank | |||
Normal rank |
Revision as of 18:27, 13 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On patching algorithms for random asymmetric travelling salesman problems |
scientific article |
Statements
On patching algorithms for random asymmetric travelling salesman problems (English)
0 references
25 June 1992
0 references
Let the arc-lengths \(\ell_{ij}\) of a complete digraph of order \(n\) be independent uniform \([0,1]\) random variables. The authors consider the patching algorithm of \textit{R. M. Karp} [SIAM J. Comput. 8, 561-573 (1979; Zbl 0427.90064)] and \textit{R. M. Karp} and \textit{J. M. Steele} [in: The travelling salesman problem, a guided tour of combinatorial optimization, 181-205 (1985; Zbl 0582.90100)] for the travelling salesman problem on such a digraph and give modifications which tighten the expected error. These ideas are also extended to the \(k\)-person travelling salesman problem [see \textit{G. Frederickson, M. Hecht} and \textit{C. Kim}, SIAM J. Comput. 7, 178-193 (1978)] and the problem of finding the minimum length closed walk through the vertex set of the digraph.
0 references
complete digraph
0 references
patching algorithm
0 references
travelling salesman
0 references
\(k\)-person travelling salesman
0 references
minimum length closed walk
0 references