TrickiHere is a principle which Professor Tao refers to as the greedy algorithm in his writing: in a sequential construction it occurs often that we have many choices for the next step. It is often helpful to pick the best or the worst possible rather than an arbitrary choice. Sometimes this is what makes a construction possible, and at other times it even gives an optimal or unique construction. Could there be an article on this? Not that there is any need for it as this is a very common theme, but I would also be happy to contribute examples to a greedy algorithm article.
I would like to make the following addition to my initial post: I didn't volunteer to write an article on the greedy algorithm because of this principle's wide application and use and because of my limited experience with it. I am sorry for the double post. Thanks!
I was planning to write something on greedy algorithms. Perhaps I'll get one started so that people can add a couple of examples. I have one rather obvious one, and if I had time I could try to explain one or two nice but less obvious ones.
An article on greedy algorithms could be a lead-in (or sub-article, or something) to a more general article on matroids and their uses in combinatorics and theoretical computer science.
Matroids are only so-so useful. Of the greedy algorithms that I've come across, only a minority of them can be expressed using matroid terminology. Greedoids, not much more.
Post new comment
(Note: commenting is not possible on this snapshot.)