atsp

On the integrality Gap of Small Asymmetric Travelling Salesman Problems: A Polyhedral and Computational Approach

  • Eleonora Vercesi
  • Luca Maria Gambardella
  • Stefano Gualandi
  • Monaldo Mastrolilli
  • Janos Barta
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags ,

    In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for small-sized instances. In particular, we focus on the geometric properties and symmetries of the ASEP polytope ( \(P_{ASEP}^n\) ) and its vertices. The polytope’s symmetries … Read more

    Upper Bounds on ATSP Neighborhood Size

  • Gregory Gutin
  • Anders Yeo
    • Categories Graphs and Matroids, Meta Heuristics Tags , , ,

    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$ … Read more