CaltechAUTHORS
  A Caltech Library Service

A Fourier space algorithm for solving quadratic assignment problems

Kondor, Risi (2010) A Fourier space algorithm for solving quadratic assignment problems. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery , New York, NY, pp. 1017-1028. ISBN 978-0-898717-01-3. https://resolver.caltech.edu/CaltechAUTHORS:20100824-080823503

[img] PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.

286Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20100824-080823503

Abstract

The quadratic assignment problem (QAP) is a central problem in 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 paper we propose a new approach to the QAP based on the theory of non–commutative Fourier analysis on the symmetric group. Specifically, we 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 O(n3) time per branch–and–bound node. The techniques underlying the algorithm generalize to a range of other combinatorial optimization problems.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://www.siam.org/proceedings/soda/2010/SODA10_082_kondorr.pdfPublisherUNSPECIFIED
Additional Information:© 2010 SIAM. The author would like to thank Rocco Servedio, Cliff Stein, Garud Iyengar, Daniel Bienstock, John Shawe- Taylor and Marconi Soares Barbosa for discussions and suggestions related to this work, as well as the anonymous reviewers for some important observations.
Record Number:CaltechAUTHORS:20100824-080823503
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20100824-080823503
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:19613
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:30 Aug 2010 16:55
Last Modified:03 Oct 2019 01:59

Repository Staff Only: item control page