In graph theory, we have long had a very similar idea, that a meaningful graph property is something preserved by any isomorphism of the graph. Another example of this, of even more direct relevance to the study of algorithms, was given by Fred Roberts in his talk on meaningfulness in epidemiology. He mentioned that shortest path algorithms are used very widely, but are only applicable when the edge weights of a graph are given by ratio data: if you can perform more general linear transformations on the edge weights, such as adding the same number to each of them, you can change the result of the shortest path computation. In contrast, minimum spanning trees, despite their very similar definition, are much more broadly meaningful. They make sense even when the edge weights are ordinal, because they depend only on the pairwise ordering of the weights, something that does not change when you apply a monotonic transformation to the weights.

11011110: Meaningfulness Tuesday, April 1, 2014 @ 11:34pm