Semidefinite code bounds based on quadruple distances

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

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