3
$\begingroup$

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 :)

$\endgroup$
  • 1
    $\begingroup$ You might want to google the relationship between Matroids and greedy algorithms. Maybe check this question $\endgroup$ – adrianN Sep 3 '17 at 6:56
  • $\begingroup$ That's a bit like asking "a general algorithm for divide & conquer algorithm". In a way, you have a type error: algorithm design principle/pattern != algorithm. That said, for greedy there actually is a canonical algorithm, as adrianN and YuvalFilmus mention. $\endgroup$ – Raphael Sep 3 '17 at 8:17
  • 3
    $\begingroup$ "After we have polished this approach" Please note that we're a question and answer site, not a discussion forum. If your goal is to collaboratively build something up, this isn't the right site. $\endgroup$ – David Richerby Sep 3 '17 at 10:46
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you should lead with the last paragraph. The canonical greedy is often what people use/want, and they should look there first. $\endgroup$ – Raphael Sep 3 '17 at 8:16
  • $\begingroup$ This is precisely the reason why people should be told about more general versions of the greedy algorithm. $\endgroup$ – Yuval Filmus Sep 3 '17 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.