Talk: "Why the Greedy algorithm works?"

What we'll do
Argimiro Arratia will peresent the paper Matroids and the greedy algorithm J. Edmonds (1971).
Argimiro Arratia is currently a professor of UPC and obtained his Ph.D in Mathematics (Wisconsin)
You can find more information about him following the next link: www.cs.upc.edu/~argimiro/

Abstract
A greedy algorithm is one of the simplest strategies to solve an optimization problem. It is based on a step-by-step selection of the best candidate (local) solution, in the hope that in the end of this process a global optimal solution is obtained. Greedy algorithms do not always output global optimal solutions, but for many optimization problems they do, in which case one says that the greedy algorithm works. Is there some criterion to know when it will work?

A result that we should love, and I will present in this talk, due to Jack Edmonds and published in 1971, states that for a greedy algorithm to output optimal solutions it is necessary and sufficient that the input is a matroid.

The intuition behind Edmonds’ result is to view the problem of determining the correctness of the greedy algorithm as a localization problem: in order to know if greedy works for some set, it suffices to check if greedy works for each of the parts of some discrete partition of the set. This is a classical working paradigm for the algebraic geometer, namely to solve problems locally and translate solutions globally, and vice versa. And a criterion that guarantees success of this local-to-global process when objects are viewed as ideals in some ring of polynomials is the Cohen-Macaulay property, which extends the concept of matroids.

More information and inscriptions.