$\newcommand{\defeq}{\mathrel{\mathop:}=}$

2008/04/28

Proving the Greedy Theorem by Fold Fusion

In hope of finally deriving algorithms for optimisation problems in AoPA, I naturally start from the Greedy Theorem and its applications, since it is the simplest yet nontrivial theorem for optimisation problems in AoP and, maybe more importantly, it involves only folds. The proof recorded in AoP makes essential use of the Hylomorphism Theorem, but it is easier (for me) to prove the theorem by fold fusion, as hinted by Shin's Proving the Thinning Theorem by Fold Fusion. In fact, being new to the material, I occasionally need to look into the blog post for directions. Therefore I must thank the extra Λ for getting Shin writing down the proof. :P

The statement of the Greedy Theorem is as follows.

We first reduce the conclusion to two fusion conditions.

The first fusion condition is an easy consequence of the fact that min R is included in the membership relation.

The second fusion condition makes use of the monotonicity condition and transitivity of R (since Rº is a preorder).

And the theorem is proven.

--
Now I need to find a suitable optimisation problem to work with...

Labels: