A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
复制标题
DOI：
10.1016/j.disopt.2013.02.003
复制
发表时间：
2013-08
期刊：
影响因子：
--
通讯作者：
Abraham P. Punnen;S. Kabadi
中科院分区：
文献类型：
--
作者：
Abraham P. Punnen;S. Kabadi
如果存在具有成本矩阵 C 的线性分配问题 (LAP) 实例，使得对于每个分配，QAP 和 LAP 目标函数值相同，则具有成本矩阵 Q 的二次分配问题 (QAP) 的实例被称为可线性化。 QAP线性化问题可以在O(n 4)时间内解决。然而，对于 Koopmans-Beckmann QAP 和乘法分配问题的特殊情况，输入大小为 Ω (n 2)。我们证明这些特殊情况的 QAP 线性化问题可以在 O (n 2) 时间内解决。对于对称 Koopmans–Beckmann QAP，Bookhold [I. Bookhold，对二次分配问题的贡献，Optimization 21 (1990) 933–943.] 给出了线性化的充分条件，并提出了该条件是否必要的问题。我们证明，Bookhold 条件对于对称 Koopmans-Beckmann QAP 的线性化也是必要的。
An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in O (n 4) time. However, for the special cases of Koopmans–Beckmann QAP and the multiplicative assignment problem the input size is of Ω (n 2). We show that the QAP linearization problem for these special cases can be solved in O (n 2) time. For symmetric Koopmans–Beckmann QAP, Bookhold [I. Bookhold, A contribution to quadratic assignment problems, Optimization 21 (1990) 933–943.] gave a sufficient condition for linearizability and raised the question if the condition is necessary. We show that Bookhold’s condition is also necessary for linearizability of symmetric Koopmans–Beckmann QAP.