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: http://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.

I will try to explain what this is, without going too deep into the mathematics, and show how this more ample algebraic concept explains when greedy works for computationally hard optimization problems like the Maximum Independent Set (to find the largest subset of vertices in a given graph which are pairwise non-adjacent), and the Coin-Exchange problem (to find the minimum number of coins, in a given monetary system, whose values sum up to a given target positive number).

References:

This talk is mostly based on my recent paper:

• A. Arratia (2018) The Greedy Algorithm and the Cohen-Macaulay property of rings, graphs and toric projective curves (To appear in the Festshrift volume for Antonio Campillo on the occasion of his 65th birthday (Springer 2018))

and the seminal paper of Jack Edmonds:

• J. Edmonds (1971) Matroids and the greedy algorithm, Math. Programming 1, 127-136

However I advise to learn Edmonds result from

• Papadimitriou and Steiglitz (1998) Combinatorial Optimization, Algorithms and Complexity (Dover)
• Cormen, Leiserson and Rivest, Introduction to Algorithms (MIT Press, 1990)

• What to bring
You don't need to bring anything especial for this meetup.

• Important to know
Reading the papers is not a must but you should come in an open minded mood :)

We have a code of conduct (https://github.com/papers-we-love/barcelona/blob/master/code-of-conduct.md) and everyone HAS to follow it. The rules are very simple: Be an adult, don't be a jerk.