Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationGreedy AlgorithmsMatroid TheoryGreedy ApproximationGreedy Heuristics
Matroids were introduced by Whitney in 1935 to try to capture abstractly the essence of dependence. Whitney's definition em- braces a surprising diversity of combinatorial structures. Moreover, ma- troids arise naturally in combinatorial optimization since they are pre- cisely the structures for which the greedy algorithm works. This survey paper introduces matroid theory, presents some of the main theorems in the subject, and identifies some of the major problems of current research interest.
36