A general algorithm for greedy algorithms

Question

I have been refreshing on greedy algorithms as an algorithm design technique. I have read many sources for an explanation of what a greedy algorithm is, because I would like to put together a general greedy algorithm.

When reading these sources, I have gathered all of the important concepts to try to come up with this general algorithm for the greedy selection technique. By "general" I mean that it summarizes the behavior of the technique for all possible problem for who this technique would yield a correct solution.

I would like some input on it. Here is take 1:

Let $f$ be a function from $S$ to any set. The following algorithm tries to perform greedy choices per each search iteration of element of $S$, in order to try come up with the best possible point for $f$ over $S$ given a set of constraints $C$:

Select p0 from S;
i := 1;
Let P be a set of already chosen points from S to be initialized to {}
Let F be the set of values of f for each element of P to be initialize to {};
while S != {}:
    Make a greedy choice for p_i based on p_{i - 1};
    if f(p_i) is feasible based on constraints from C and has improved:
        p_{i - 1} := p_i;
    Add f_i := f(p_i) to F;
    Remove p_{i - 1} from S and save it in P;
 return P, F;

My specific question is: How far is this first take from being a correct generalization of the greedy selection technique for algorithmic design?

This should be fun :)

Answer 1

There is no such thing as the correct generalization of the greedy selection technique, because it's an informal technique. That said, there has been some effort at modeling the greedy heuristic, with a view toward understanding its limitations. This study has been initiated by Borodin, Nielsen and Rackoff, (Incremental) priority algorithms, and continued mostly by Borodin and his coauthors.

Before discussing the work of Borodin et al., let me briefly mention the subject of matroids and greedoids. They answer the following question:

Consider the greedy algorithm for maximizing a linear objective subject to constraints. For which constraint structure does this algorithm produce optimal results?

We can think of the constraints as a set system, any member of which is a feasible solution. For hereditary set systems (any subset of a feasible set is feasible), the greedy algorithm produces an optimal result if and only if the constraints form a matroid. Greedoids answer a more refined question.

Back to Borodin's priority algorithms. The exact definition of a priority algorithm depends on the context, but here is a general flavor. There is some iterative procedure for constructing a solution for a given instance. The instance consists of a set of objects (think scheduling algorithms). At each step of the procedure, the algorithm chooses an ordering of all objects, and the best available object according to the ordering is added to the solution set. All objects incompatible with this object are thrown out, and the following iteration is executed. The process stop when the set of available objects becomes empty.

What I described above is the adaptive priority model. In the fixed priority model, the ordering is chosen once and for all rather than at each step. In both models, the algorithm is not allowed to look at the set of available objects (that would be cheating).

The situation for graph algorithms is somewhat more complicated, see for example Borodin, Boyar and Larsen, Priority algorithms for graph optimization problems, and there are several models which are more realistic than the model considered above. There are several other variants of priority algorithms which can be explored through the relevant work of Borodin and others.