[Colloquium] [Staff] Theory Seminars at Computer Science
Donna Brooms
donna at cs.uchicago.edu
Tue Nov 8 07:19:35 CST 2011
~REMINDER~
COMPUTER SCIENCE
The University of Chicago
THEORY SEMINAR
-----------------------------------
Date: Tuesday, November 8, 2011
Time: 3 p.m.
Place: Ryerson 251, 1100 E. 58th Street
------------------------------------
Speaker: Risi Kondor
From: University of Chicago
Title: Solving the Quadratic Assignment Problem in Fourier Space
Abstract: 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.
______________________________________________________________________
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
Persons who need assistance should call 773-702-6614
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20111108/b2566e09/attachment.htm
More information about the Colloquium
mailing list