Upper Bounds on ATSP Neighborhood Size

Gregory Gutin (G.Gutinrhul.ac.uk)
Anders Yeo (yeodaimi.au.dk)

Abstract: We consider the Asymmetric Traveling Salesman Problem (ATSP) and use the definition of neighborhood by Deineko and Woeginger (see Math. Programming 87 (2000) 519-542). 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$\neq$NP. We prove that $\mu(n) < \beta (n-k)!$ for any fixed integer $k\ge 1$ and constant $\beta >0$ provided NP$\not\subseteq$P/poly, which (like P$\neq$NP) is believed to be true. We also give upper bounds for the size of an ATSP neighborhood depending on its search time.

Keywords: ATSP, TSP, exponential neighborhoods, upper bounds

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Combinatorial Optimization (Meta Heuristics )

Citation: Technical Report TR-01-01, Dept of Computer Science, Royal Holloway University of London, UK, April 2001

Download: [Postscript]

Entry Submitted: 04/24/2001
Entry Accepted: 04/24/2001
Entry Last Modified: 04/24/2001

Modify/Update this entry