论文标题
关于QAP-Polytope的某些方面定义不平等的复杂性
On the Complexity of Some Facet-Defining Inequalities of the QAP-polytope
论文作者
论文摘要
二次分配问题（QAP）是一个众所周知的NP - 硬性问题，相当于在QAP polytope上优化线性目标函数。带有参数$ n $ - \ qappolyTope {n}的QAP多层底座定义为rank hull of Rank -$ 1 $矩阵$ xx^t $ at $ x $，为vectorized $ n \ times n \ times n $ n $置换矩阵。 在本文中，我们考虑了QAP-Polytope的所有已知的指数尺寸的家庭。我们描述了一个新的有效不平等的家族，我们表明是定义的。我们还表明，对某些已知类别的不平等类别的会员资格测试（并因此优化）是综合的。我们通过显示\ qappolytope {n}的所有放松的扩展复杂性，以$ 2^{ω（n）} $显示$ 2^{ω（n）} $的下限来补充我们的硬度结果。
The Quadratic Assignment Problem (QAP) is a well-known NP-hard problem that is equivalent to optimizing a linear objective function over the QAP polytope. The QAP polytope with parameter $n$ - \qappolytope{n} - is defined as the convex hull of rank-$1$ matrices $xx^T$ with $x$ as the vectorized $n\times n$ permutation matrices. In this paper we consider all the known exponential-sized families of facet-defining inequalities of the QAP-polytope. We describe a new family of valid inequalities that we show to be facet-defining. We also show that membership testing (and hence optimizing) over some of the known classes of inequalities is coNP-complete. We complement our hardness results by showing a lower bound of $2^{Ω(n)}$ on the extension complexity of all relaxations of \qappolytope{n} for which any of the known classes of inequalities are valid.
