You are here: Home Kolloquium A unified FFT-based approach to higher order assignment problems

A unified FFT-based approach to higher order assignment problems

Prof. Dr. Michael Clausen, Universität Bonn/Fraunhofer FKIE

Event details
    When Jan 27, 2020
    from 16:00 to 17:30
    Where Hörsaal 7, Endenicher Allee 19c, 53115 Bonn
    Add event to calendar vCal

    In my talk I will introduce the cross-correlation between two discrete complex-valued functions whose common domain is a set on which a finite group acts transitively. Such a group action generalizes, e.g., circular time shifts for discrete periodic time signals or spatial translations in the context of image processing. Cross-correlations can be reformulated as convolutions in group algebras and are thus transformable into the spectral domain via (fast) discrete Fourier transforms.  The resulting general discrete cross-correlation theorem will serve as the basis for a unified approach to two classes of higher order assignment problems. The “simplest” representatives of these classes are the NP-hard symmetric and asymmetric quadratic assignment problem. I will present a systematic spectral approach in terms of the representation theory of symmetric groups to solve such assignment problems.

    Document Actions