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

DOI10.1016/j.jsc.2021.07.004zbMath1491.65176OpenAlexW3189804607MaRDI QIDQ820943

Michael Clausen

Publication date: 29 September 2021

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2021.07.004

zbMATH Keywords

convolutionassignment problemsFFTcross-correlationfinite group actionsrepresentation theory of symmetric groups

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Representations of finite symmetric groups (20C30) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Numerical methods for discrete and fast Fourier transforms (65T50)

Cites Work

• Geometry, complexity, and combinatorics of permutation polytopes
• Computing Fourier transforms and convolutions of \(S_{n - 1}\)-invariant signals on \(S_n\) in time linear in \(n\)
• Multivariate polynomials, standard tableaux, and representations of symmetric groups
• On the Snapper/Liebler-Vitale/Lam theorem on permutation representations of the symmetric group
• Young diagrams, Schur functions, the Gale-Ryser theorem and a conjecture or Snapper
• Convex hulls of orbits of representations of finite groups and combinatorial optimization
• A GRASP for the biquadratic assignment problem
• Fast Fourier transform for fitness landscapes
• Ordering the partition characters of the symmetric group
• Linear time Fourier transforms of \(S_{n-k}\)-invariant functions on the symmetric group \(S_n\)
• Fast multiplication of large numbers
• Integer multiplication in time \(O(n\log n)\)
• Modern Computer Algebra
• Assignment Problems and the Location of Economic Activities
• Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm
• P-Complete Approximation Problems
• Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
• The efficient computation of Fourier transforms on the symmetric group
• Computing Isotypic Projections with the Lanczos Iteration
• Reducibility among Combinatorial Problems
• The Hook Graphs of the Symmetric Group
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item