Previous: The pairing step Up: The pairing step Next: Stable Marriage algorithm

Greedy algorithm

The greedy method is a local optimization method. It assumes that the path to the best global optimum is a series of locally optimal steps. At each step, one adds the pairing that has the next shortest distance.

The problem of pairing things up does not have the greedy property, so the algorithm doesn't work. It does produce pairings of some kind, and is easy to implement. The running time is .