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

DOI10.1016/J.JSC.2021.07.004MaRDI QIDQ820943zbMATH OpenOpenAlexFDO

Authors 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

assignment problemsconvolutioncross-correlationFFTfinite group actionsrepresentation theory of symmetric groups

Mathematics Subject Classification ID

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

Recommendations

• A Fourier space algorithm for solving quadratic assignment problems
• scientific article; zbMATH DE number 4158391
• Fast Fourier transform for fitness landscapes
• scientific article; zbMATH DE number 475354
• The Newton sums method in combinatorial optimization

Cites work

• A Fourier space algorithm for solving quadratic assignment problems
• A GRASP for the biquadratic assignment problem
• Assignment Problems and the Location of Economic Activities
• Computing Fourier transforms and convolutions of \(S_{n - 1}\)-invariant signals on \(S_n\) in time linear in \(n\)
• Computing Isotypic Projections with the Lanczos Iteration
• Convex hulls of orbits of representations of finite groups and combinatorial optimization
• Fast Fourier transform for fitness landscapes
• Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
• Fast multiplication of large numbers
• Faster integer multiplication
• Geometry, complexity, and combinatorics of permutation polytopes
• scientific article; zbMATH DE number 4158391 (Why is no real title available?)
• scientific article; zbMATH DE number 3771876 (Why is no real title available?)
• scientific article; zbMATH DE number 124861 (Why is no real title available?)
• scientific article; zbMATH DE number 610966 (Why is no real title available?)
• scientific article; zbMATH DE number 714526 (Why is no real title available?)
• scientific article; zbMATH DE number 714530 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 1568992 (Why is no real title available?)
• Integer multiplication in time \(O(n\log n)\)
• Linear time Fourier transforms of \(S_{n-k}\)-invariant functions on the symmetric group \(S_n\)
• Modern computer algebra
• Multivariate polynomials, standard tableaux, and representations of symmetric groups
• On the maximum quadratic assignment problem
• On the Snapper/Liebler-Vitale/Lam theorem on permutation representations of the symmetric group
• Ordering the partition characters of the symmetric group
• P-Complete Approximation Problems
• Reducibility among combinatorial problems
• The efficient computation of Fourier transforms on the symmetric group
• The Hook Graphs of the Symmetric Group
• Young diagrams, Schur functions, the Gale-Ryser theorem and a conjecture or Snapper

This page was built for publication: A unified FFT-based approach to maximum assignment problems related to transitive finite group actions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820943)