This seriation method reorganizes the D matrix by itertively
placing the smallest distances in matrix D in the n1 cells
contiguous to the diagonal:
This is a greedy approach, with n1 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 multifragment 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 n1
steps of the seriation algorithm is associated with one of the n1
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 subtrees borne by the associated branch.
The two subtrees 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, 387411.
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. 186201.
Gruvaeus, G. and Wainer, H. (1972) Two additions to hierarchical cluster analysis. British Journal of Mathematical and Statistical Psychology, 25, 200206.
PermutMatrix 

TOP 