greedy algorithms are a popular choice for solving problems because they are often simple, intuitive, and efficient. however, they can also be misleading, sometimes yielding the worst possible solution to a problem. in this talk we'll go through some examples of greedy algorithms (we'll look at the best example first, and go from there) and discuss when they perform terribly, optimally, and when we can bound how close the greedy solution is to the optimal solution. finally, we'll review what matroids are and prove that a greedy algorithm yields an optimal solution to a particular class of problems if and only if we can rephrase the problem as a statement about a matroids. sponsored by the gsa.