Multiple-fragment heuristic (MF) (What is seriation ?)

This seriation method reorganizes the D matrix by itertively placing the smallest distances in matrix D in the n-1 cells contiguous to the diagonal:
                  
This is a greedy approach, with n-1 steps.
At each step, rows i and columns j in D are moved so that the smallest distance is placed in a not yet allocated cell. The smallest distance is not chosen freely. It is constrained by the necessity to keep the already allocated cells in place.
This sequential procedure corresponds to the approach proposed by Gelfand (1971), in the context of the seriation of archaeological objects, and to the multi-fragment heuristic (Bentley 1992) for the traveling salesman problem (TSP).

This heuristic do not garantee to find an optimal solution but give quickly a "reasonable good" solution. This solution could be improved by a local search heuristic.

If seriation is done under tree constraint, each of the n-1 steps of the seriation algorithm is associated with one of the n-1 internal branches of the tree.
At each step, placing the smallest distance adjacent to the diagonal is equivalent to choosing the position of the two sub-trees borne by the associated branch. The two sub-trees are positioned so that the two elements put side by side are the closest according to D.
This corresponds to the dendrogram reorganization procedure proposed by Gruvaeus and Wainer (1972).

References :

Bentley, J. L. (1992) Fast Algorithms for Geometric Traveling Salesman Problems. ORSA Journal on Computing, 4, 387-411.

Gelfand, A. E. (1971) Rapid seriation methods with archaelogical application. In Hodson, F. R., Kendall, D. G. and Tautu (eds), Mathematics in the archaeological and historical Sciences. Edimburg University Press, Edimburg, pp. 186-201.

Gruvaeus, G. and Wainer, H. (1972) Two additions to hierarchical cluster analysis. British Journal of Mathematical and Statistical Psychology, 25, 200-206.

PermutMatrix 
TOP