A Fourier space algorithm for solving quadratic assignment problems
A Fourier space algorithm for solving quadratic assignment problems
复制标题
求解二次分配问题的傅立叶空间算法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
R. Kondor
中科院分区：
文献类型：
--
作者：
R. Kondor
二次分配问题是组合优化中的一个核心问题。几个著名的计算困难的任务，如图匹配，分区，和旅行推销员都减少到特殊情况下的QAP。
在本文中，我们提出了一种新的方法来QAP的对称群上的非交换傅立叶分析理论的基础上。具体来说，我们提出了一个分支定界算法，在傅立叶空间中执行分支和定界步骤。
通过利用QAP目标函数的带限性质并使用FFT技术，该算法在每个分支定界节点的O（n3）时间内运行。该算法的技术基础推广到一系列其他组合优化问题。
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.