Anti-matroids

Abstract

We introduce an anti-matroid as a family 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 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.