[期刊论文][Full-length article]


A unified FFT-based approach to maximum assignment problems related to transitive finite group actions

作   者:
Michael Clausen;

出版年:2022

页     码:88 - 115
出版社:Elsevier BV


摘   要:

This paper studies the cross-correlation of two real-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 Fourier Transforms. The resulting general discrete cross-correlation theorem will serve as the basis for a unified FFT-based approach to maximum assignment problems related to transitive finite group actions. Our main focus is on those assignment problems arising from the actions of symmetric groups on the cosets of Young subgroups. The “simplest” nontrivial representatives of the latter class of problems are the NP-hard symmetric and asymmetric maximum quadratic assignment problem. We present a systematic spectral approach in terms of the representation theory of symmetric groups to solve such assignment problems. This generalizes and algorithmically improves Kondor's spectral branch-and-bound approach (SODA, 2010) to the exact solution of the asymmetric maximum quadratic assignment problem.



关键字:

Finite group actions ; Convolution ; FFT ; Cross-correlation ; Assignment problems ; Representation theory of symmetric groups


所属期刊
Journal of Symbolic Computation
ISSN: 0747-7171
来自:Elsevier BV