upper bounds

Semidefinite code bounds based on quadruple distances

  • Dion C. Gijswijt
  • Hans D Mittelmann
  • Alexander Schrijver
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    Let A(n, d) be the maximum number of 0, 1 words of length n, any two having Hamming distance at least d. We prove A(20, 8) = 256, which implies that the quadruply shortened Golay code is optimal. Moreover, we show A(18, 6) ≤ 673, A(19, 6) ≤ 1237, A(20, 6) ≤ 2279, A(23, 6) … 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