We introduce an anti-matroid as a family $\cal F$ of subsets of a ground set $E$ for which there exists an assignment of weights to the elements of $E$ such that the greedy algorithm to compute a maximal set (with respect to inclusion) in $\cal F$ of minimum weight finds, instead, the unique maximal set … 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