Anti-matroids

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 of maximum weight. We introduce a special class of anti-matroids, $I$-anti-matroids, and show that the Asymmetric and Symmetric TSP as well as the Assignment Problem are $I$-anti-matroids.

Article

Download

View Anti-matroids