traveling salesman problem

On semidefinite programming relaxations of the traveling salesman problem

  • Etienne de Klerk
  • Renata Sotirov
  • Dmitrii V. Pasechnik
    • Categories Combinatorial Optimization, Semi-definite Programming Tags ,

    We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP), obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in the paper: [D. Cvetkovic, M. Cangalovic and V. Kovacevic-Vucic. Semidefinite Programming Methods for the Symmetric Traveling Salesman … Read more

    Solving a combinatorial problem using a local optimization in ant based system

  • D. Dumitrescu
  • C-M. Pintea
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    Local optimizations introduced to obtain improved tours for Traveling Salesman Problem have a great impact on the final solution. That is way we introduce a new ant system algorithm with a new local updating pheromone rule, and the tours are improved using k-opt techniques. The tests use different parameters, in order to obtain solutions close … Read more

    On cost matrices with two and three distinct values of Hamiltonian paths and cycles

  • Santosh N. Kabadi
  • Abraham Punnen
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    Polynomially testable characterization of cost matrices associated with a complete digraph on $n$ nodes such that all the Hamiltonian cycles (tours) have the same cost is well known. Tarasov~\cite{TARA81} obtained a characterization of cost matrices where tour costs take two distinct values. We provide a simple alternative characterization of such cost matrices that can be … Read more