Further talks

Modal title

Modal content

Date / Time

Speaker

Title

Location

3 October 2014
11:00-12:00

Matteo Seminaroti
Centrum Wiskunde & Informatica, Amsterdam, NL

Details

Title	QAP and recognition of Robinsonian matrices
Speaker, Affiliation	Matteo Seminaroti, Centrum Wiskunde & Informatica, Amsterdam, NL
Date, Time	3 October 2014, 11:00-12:00
Location	HG G 19.2
Abstract	A Robinson similarity matrix is a symmetric matrix whose entries decrease monotonically along rows and columns when moving away from the diagonal. A matrix is said to be a Robinsonian similarity if its rows and columns can be symmetrically permuted to obtain a Robinson similarity. Robinsonian matrices arise in the classical seriation problem and play an important role in any practical problem where unsorted similarity information must be reordered. We show that the Quadratic Assignment Problem in Koopmans-Beckman form QAP(A,B) over Robinsonian matrices is solved by the permutation reordering the matrices as Robinson matrices. Furthermore, we present a new polynomial time algorithm to find such permutations, based on a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. The algorithm is based essentially on partition refinements and Lexicographic-Breadth-First-Search (LBFS).

QAP and recognition of Robinsonian matricesread_more

Notes: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archive: undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined