Upper bounds on ATSP neighborhood size. (Q1406047)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Upper bounds on ATSP neighborhood size. |
scientific article |
Statements
Upper bounds on ATSP neighborhood size. (English)
0 references
9 September 2003
0 references
We consider the Asymmetric Traveling Salesman Problem (ATSP) and use the definition of neighborhood by \textit{V. G. Deineko} and \textit{G. J. Woeginger} [Math. Program. 87, No. 3 (A), 519--542 (2000; Zbl 1043.90075)]. Let \(\mu(n)\) be the maximum cardinality of polynomial time searchable neighborhood for the ATSP on \(n\) vertices. Deineko and Woeginger conjectured that \(\mu(n)<\beta(n-1)!\) for any constant \(\beta>0\) provided P\(\not=\)NP. We prove that \(\mu(n)<\beta(n-k)!\) for any fixed integer \(k\geq 1\) and constant \(\beta>0\) provided NP is neither a subset of nor equal to P/poly, which (like P\(\not=\)NP) is believed to be true. We also give upper bounds for the size of an ATSP neighborhood depending on its search time.
0 references
ATSP
0 references
TSP
0 references
Exponential neighborhoods
0 references
Upper bounds
0 references
0 references
0 references
0 references
0 references
0 references