A unified FFT-based approach to maximum assignment problems related to transitive finite group actions. (March 2022)

• Record Type: Journal Article
• Authors: Clausen, Michael
• Is Part Of: Journal of symbolic computation. Volume 109(2022)
• Page Start: 88
• Page End: 115
• Publication Date: 2022-03
• Subjects: 05E10 -- 20C30 -- 65T50 -- 68W30 -- 90B80 -- 90C27; Finite group actions -- Convolution -- FFT -- Cross-correlation -- Assignment problems -- Representation theory of symmetric groups; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2021.07.004
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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.