A new understanding of greed
Prasad Ram · 1993
The pervasiveness of greedy algorithms is due to their simplicity. It is incomprehensible that a complex theory (e.g. matroids, greedoids) underlies the class of optimization problems that can be solved using greedy algorithms. It seems impossible to reconcile one's intuitive understanding of greedy algorithms with the existing formalisms of greed. We propose a radically different approach to understanding greed. Relating greed to majorization, exchange matrices and Schur-convex functions has both the right intuitive appeal and the simplicity exhibited by greedy algorithms. This new characterization greedy solvable problems also sets the stage for better understanding of optimization problems for which greedy solutions serve as good heuristics. Majorization has thus far been defined as a preorder relation on sorted sequences. This definition is too restrictive for our purposes. We extend the definition of majorization to be a partial order relation that relates two arbitrary sequences. The informal notion of greedy choice property and optimal substructure property associated with optimal answers to greedy solvable optimization problems is formalized in terms of majorization defined on arbitrary sequences. We also show that characterization of greedy solvable problem in terms of majorization, exchange matrices and Schur-convex functions subsumes the existing formalisms such as matroids, greedoids and submodular functions.