There's a large class of global optimisation algorithms which share a common dynamic-programming sort of approach.

The general approach works for any situation in which you need to find a property of a list of items, when that property is such that you can find it for a given list if you already know it for all of that list's initial (or sometimes final) segments. So you work your way along the list, computing your property for increasingly long initial (or final) segments of it; and at each stage, you have all the results from the previous stages stored, so you typically need at worst O(N) time to compute the property this time.

It sounds almost too obvious to dignify with a name, put like that; but it turns out that this basic algorithm structure lends itself to quite a few surprisingly useful applications, many in the field of global optimisation.

My usual example is the optimal paragraph wrapping algorithm used in TeX. Work backwards along the paragraph word by word; at each stage, decide how you would optimally (according to some complex cost function) wrap the paragraph from this word onwards if this word appeared at the start of a line. You do this by going through the possible positions for the first line break, and for each candidate you refer to your previously stored answer for all the words after that point. So you end up with the global optimum choice of line break positions to minimise your cost function over the whole paragraph. Assuming the number of words per line is bounded (which it will be, in practice), this takes linear time.

A few years ago I designed a font in which most characters had several possible glyphs, and wrote an optimising font engine to analyse a string of text and find the best assignment of glyphs to characters subject to a value function and some constraints about which glyphs looked unacceptably poor next to each other. I derived a linear-time true global optimisation algorithm for this problem by thinking about the TeX paragraph formatting algorithm.

Quite recently I came up against the following question: if you have a finite list of items, and a partial order defined on those items but independent of the actual ordering of the list, how can you pick out the longest (not necessarily contiguous) subsequence of the list which is totally ordered with respect to the partial order? Another algorithm of this class solves that one: for each element of the list in turn, find the longest totally ordered subsequence which terminates in that exact element, and then pick whichever of those came out longest in all. At each stage you have to go back over all of the previously computed subsequences, so this one takes quadratic time; but it's still a lot better than the exponential brute force approach I had previously tried!

The Viterbi algorithm for probabilistic inference is also of this form. That's not my field at all: I only found out about it because I was describing one of the above algorithms to ptc24, and he said ‘Oh, you mean like the Viterbi algorithm?’. And, it turned out, indeed I did.

An important thing to note about all of the above is that they are true global optimisers. They're not greedy algorithms which do a basically good but undistinguished job; they're not incremental strategies which reliably find their way to the top of some hill but might miss a taller mountain elsewhere; they're not approximate methods like simulated annealing which only probabilistically find the best answer. These algorithms are all perfect: whatever answer exists and has the highest score, they will find. And they typically do it in linear or at worst quadratic time, which makes them essentially indispensable for any application to which they are suited.

So because these things keep coming up, and in particular because I keep finding applications of the same principle to solve problems I'm faced with, I would like there to be a piece of terminology that precisely describes this particular optimisation strategy.

‘Dynamic programming’ is of course an umbrella term which covers all of the above. But it's too general: it also describes other types of algorithm which don't fit into this specific framework. I want a word for this specific shape of dynamic programming algorithm. The best I currently have is ‘Viterbi-like’, and that's useless because even I wouldn't have known what it meant until a couple of years ago.