Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  2 Dec 2016 
Place of Publication  Tilburg 
Publisher  
Print ISBNs  9789056684969 
Publication status  Published  2016 
Fingerprint
Cite this
}
Combinatorial algorithms for the seriation problem. / Seminaroti, Matteo.
Tilburg : CentER, Center for Economic Research, 2016. 219 p.Research output: Thesis › Doctoral Thesis
TY  THES
T1  Combinatorial algorithms for the seriation problem
AU  Seminaroti, Matteo
PY  2016
Y1  2016
N2  In this thesis we study the seriation problem, a combinatorial problem arising in data analysis, which asks to sequence a set of objects in such a way that similar objects are ordered close to each other. We focus on the combinatorial structure and properties of Robinsonian matrices, a special class of structured matrices which best achieve the seriation goal. Our contribution is both theoretical and practical, with a particular emphasis on algorithms. In Chapter 2 we introduce basic concepts about graphs, permutations and proximity matrices used throughout the thesis. In Chapter 3 we present Robinsonian matrices, discussing their characterizations and recognition algorithms existing in the literature. In Chapter 4 we discuss Lexicographic BreadthFirst search (LexBFS), a special graph traversal algorithm used in multisweep algorithms for the recognition of several classes of graphs. In Chapter 5 we introduce a new LexBFS based algorithm to recognize Robinsonian matrices, which is derived from a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. In Chapter 6 we introduce the novel SimilarityFirst Search algorithm (SFS), a weighted version of LexBFS which we use in a multisweep algorithm for the recognition of Robinsonian matrices. In Chapter 7 we model the seriation problem as an instance of Quadratic Assignment Problem (QAP) and we show that if the data has a Robinsonian structure, then one can find an optimal solution for QAP using a Robinsonian recognition algorithm. In Chapter 8 we discuss how to solve the seriation problem when the data does not have a Robinsonian structure, by finding a Robinsonian approximation of the original data. Finally, in Chapter 9 we discuss some experiments which we have carried out in order to compare the performance of the algorithms introduced in the thesis.
AB  In this thesis we study the seriation problem, a combinatorial problem arising in data analysis, which asks to sequence a set of objects in such a way that similar objects are ordered close to each other. We focus on the combinatorial structure and properties of Robinsonian matrices, a special class of structured matrices which best achieve the seriation goal. Our contribution is both theoretical and practical, with a particular emphasis on algorithms. In Chapter 2 we introduce basic concepts about graphs, permutations and proximity matrices used throughout the thesis. In Chapter 3 we present Robinsonian matrices, discussing their characterizations and recognition algorithms existing in the literature. In Chapter 4 we discuss Lexicographic BreadthFirst search (LexBFS), a special graph traversal algorithm used in multisweep algorithms for the recognition of several classes of graphs. In Chapter 5 we introduce a new LexBFS based algorithm to recognize Robinsonian matrices, which is derived from a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. In Chapter 6 we introduce the novel SimilarityFirst Search algorithm (SFS), a weighted version of LexBFS which we use in a multisweep algorithm for the recognition of Robinsonian matrices. In Chapter 7 we model the seriation problem as an instance of Quadratic Assignment Problem (QAP) and we show that if the data has a Robinsonian structure, then one can find an optimal solution for QAP using a Robinsonian recognition algorithm. In Chapter 8 we discuss how to solve the seriation problem when the data does not have a Robinsonian structure, by finding a Robinsonian approximation of the original data. Finally, in Chapter 9 we discuss some experiments which we have carried out in order to compare the performance of the algorithms introduced in the thesis.
M3  Doctoral Thesis
SN  9789056684969
T3  CentER Dissertation Series
PB  CentER, Center for Economic Research
CY  Tilburg
ER 