On the approximability of the traveling salesman problem (Q2495698): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Jozef Vyskoč / rank | |||
Property / reviewed by | |||
Property / reviewed by: Jozef Vyskoč / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-006-0008-z / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2059222268 / rank | |||
Normal rank |
Latest revision as of 01:06, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the approximability of the traveling salesman problem |
scientific article |
Statements
On the approximability of the traveling salesman problem (English)
0 references
2 January 2007
0 references
In the paper the previously known inapproximability bounds for symmetric as well as asymmetric traveling salesman problems are improved by more than an order of magnitude. First, a new inapproximability bound for the asymmetric traveling salesman problem is given by providing a special reduction from maximum satisfiability of linear equations modulo 2 with three variables per equation. The reduction relies on a probabilistic construction of a graph with specialized properties, the so-called \(b\)-pusher, and is essentially nonconstructive. The same basic ideas (with a new set of gadgets) are then used to prove a new inapproximability bound for the symmetric traveling salesman problem.
0 references
traveling salesman problem
0 references
inapproximability
0 references
lower bound
0 references
reduction
0 references
\(b\)-pusher
0 references