Anti-matroids

Gregory Gutin (G.Gutinrhul.ac.uk)
Anders Yeo (yeodaimi.au.dk)

Abstract: 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.

Keywords: Greedy algorithm, combinatorial optimization, TSP,

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Combinatorial Optimization (Other )

Citation:

Download: [Postscript]

Entry Submitted: 08/09/2001
Entry Accepted: 08/09/2001
Entry Last Modified: 08/09/2001

Modify/Update this entry