The quadratic assignment problem (QAP) is one of the central problems of combinatorial optimization. Several famous computationally hard tasks, such as graph matching, partitioning, and the traveling salesman all reduce to special cases of the QAP.

In this talk I describe a new approach to the QAP based on the theory of non-commutative Fourier analysis on the symmetric group. Specifically, I present a branch-and-bound algorithm that performs both the branching and the bounding steps in Fourier space.

By exploiting the band-limited nature of the QAP objective function and using FFT techniques, the algorithm runs in \m{O(n^3)} time per branch-and-bound node, which matches the complexity of standard methods, but preliminary experiments suggests that on some special classes of problems the Fourier approach visits far fewer nodes. The techniques underlying the algorithm generalize to a range of other combinatorial optimization problems.