Performance Evaluation of a Convex Relaxation Approach to the Quadratic Assignment of Relational Object Views

Schellewald, Christian ; Roth, Stefan ; Schnörr, Christoph

Document Type: Working paper
Year of publication: 2002
The title of a journal, publication series: Technical Reports
Volume: 2/2002
Place of publication: Mannheim
Publication language: English
Institution: School of Business Informatics and Mathematics > Bildverarbeitung, Mustererkennung u. Computergrafik (Schnörr 1999-2008)
MADOC publication series: Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Subject: 004 Computer science, internet
Abstract: We introduce a recently published convex relaxation approach for the quadratic assignment problem to the field of computer vision. Due to convexity, a favourable property of this approach is the absence of any tuning parameters and the computation of high–quality combinatorial solutions by solving a mathematically simple optimization problem. Furthermore, the relaxation step always computes a tight lower bound of the objective function and thus can additionally be used as an efficient subroutine of an exact search algorithm. We report the results of both established benchmark experiments from combinatorial mathematics and random ground-truth experiments using computer-generated graphs. For comparison, a recently published deterministic annealing approach is investigated as well. Both approaches show similarly good performance. In contrast to the convex ap- proach, however, the annealing approach yields no problem relaxation, and four parame- ters have to be tuned by hand for the annealing algorithm to become competitive.

Dieser Eintrag ist Teil der Universitätsbibliographie.

Metadata export


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item