Gutin, Gregory and Yeo, A. (2002) Anti-matroids. Operations Research Letters, 30 (2).
Full text access: Open
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.
This is a Submitted version This version's date is: 2002 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/f107ad17-671e-9396-a8a0-0af27346c486/5/
Deposited by Research Information System (atira) on 03-Jul-2014 in Royal Holloway Research Online.Last modified on 03-Jul-2014