greedy-choice property

The property of a problem that a globally best solution can always be reached by making the locally best choice at each step.

In more detail

When it holds, a greedy algorithm is correct and usually fast. It holds for interval scheduling and Huffman coding but not for coin change with arbitrary coins. The usual way to prove it is an exchange argument.

Related terms

Taught in

References