ABSTRACT
Greedy algorithms are often the first algorithm that one considers for various optimization problems, and, in particular, covering problems. The idea is very simple: try to build a solution incrementally by augmenting a partial solution. In each iteration, select the “best” augmentation according to a simple criterion. The term greedy is used because the most common criterion is to select an augmentation that minimizes the ratio of “cost” to “advantage.” We refer to the cost-to-advantage ratio of an augmentation as the density of the augmentation.
