Scrum is a Greedy Algorithm

Today I’d like to share with you one very algorithmic interpretation of the Scrum process being an optimization problem: it’s analogy with a Greedy Algorithm.

Greedy Algorithm Definition

A greedy algorithm repeatedly executes a procedure which tries to maximize the return based on examining local conditions, with the hope that the outcome will lead to a desired outcome for the global problem. In some cases such a strategy is guaranteed to offer optimal solutions, and in some other cases it may provide a compromise that produces acceptable approximations. [source]

If the algorithm is proved to actually find the global solution, it’s said to have the greedy choice property.

A problem can only have a working Greedy algorithm if has Optimal substructure, i.e if an optimal solution to the problem contains optimal solutions to the sub-problems.

The advantage of a Greedy algorithm is that the choice for the next step can be made very fast. But Greedy algorithms may only find local solutions (if it’s not proven to have the greedy choice property. An alternative to Greedy Algorithms is Dynamic Programming where all sub-problems are investigated and combined.

For example job scheduler use Greedy algorithms like ‘shortest first’ or ’round robbin’.

Scrum seen as an Algorithm

The Scrum algorithm could be presented very simplified as follows:

1. Sort backlog with respect to the stories’ highest business values
2. Estimate the topmost backlog item
3. Add it to the sprint scope, if total effort < sprint capacity. Repeat with #2
4. Deliver shippable increment
5. Start all over again

Here: backlog items are the candidate set, #2 is the selection function, #3 the feasibility function

If Scrum is seen like that, the question arises which solution will be found or if Scrum finds a solution at all.

Probably it won’t yield the (globally) optimal solution, as the problems are typically too complex to have an optimal substructure. But experience shows that at least it’ll find a nice (locally optimal) solution.

Essential in finding a solution is how the backlog is created and maintained and how the next (locally optimal) stories are selected.

Academic Background

Definitions

A problem is a relation from some input set  I={I_i} to an output setO={O_j} obeyeing the feasibility property P.

An algorithm A solves a problem if A produces an feasible output (i.e. obeyes P) for every input.

Let opt(w) for all w ∈ O some optimization function.

An optimal solution is w ∈ O with opt(w) being maximal or minimal.

An optimization problem is a problem finding one optimal solution. There can be more than one optimal solution.

Optimization problems are typically solved by

• trying all solutions (backtracking)
• divide into smaller problems (dynamic programming)
• construct a solution from small steps (greedy algorithms)

Prove of correctness

To prove that a greedy algorithms does actually find an optimal solution the following two properties needs to be proved:

• Greedy choice property
• Optimal substructure property

Further reading

• http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI.pdf
• http://people.cs.umass.edu/~barring/cs611/lecture/4.pdf
• http://www.cas.mcmaster.ca/~deza/graphgreedy1.pdf
• http://www.eurecom.fr/~michiard/teaching/slides/algodesign/lecture-3.pdf