[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

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/20111107/c44648a7/attachment.htm