[Back]

G. Sedlecky:
"Seriation: Exakte und heuristische Lösungsmethoden";
Supervisor: A. Mehlmann; Institut für Wirtschaftsmathematik, 2010; final examination: 2010-01-21.

Seriation describes the process of ordering a series of objects by similarity or dissimilarity.
This Problem rst occured in archaeology, where artifacts have to be ordered
by their chronological appearance. Nowadays, Seriation takes part in a wide range of
applications and is a basic tool for combinatorial data analysis. Although the problem
is simple in its formulation, possible solutions grow rapidly as the number of
objects raise, so e ective algorithms for solving this NP-hard problem are needed. In
this paper some common methods of Operations Research are presented that can be
e ectively used for Seriation. Alongside exact algorithms some e cient heuristics and
two special methods, a hierarchical clustering approach and the formulation of the
Seriation Problem as a Traveling Salesman Problem are presented.

seriation, combinatorial data analysis, operations research