A matroid is a combinatorial structure that generalizes the notion of linear independence in vector spaces to arbitrary sets, allowing for a unified approach to optimization and greedy algorithms. It is defined by a set and a collection of subsets that satisfy certain axioms analogous to the properties of linearly independent sets in vector spaces.