We study approximation algorithms for two natural generalizations of the Maximum Quadratic Assignment Problem (MaxQAP). In the Maximum List-Restricted Quadratic Assignment Problem, each node in one partite set may only be matched to nodes from a prescribed list. For instances on $n$ nodes where every list has size at least $n - O(\sqrt{n})$, we design a randomized $O(\sqrt{n})$-approximation algorithm based on the linear-programming relaxation and randomized rounding framework of Makarychev, Manokaran, and Sviridenko. In the Maximum Quadratic $b$-Matching Assignment Problem, we seek a $b$-matching that maximizes the MaxQAP objective. We refine the standard MaxQAP relaxation and combine randomized rounding over $b$ independent iterations with a polynomial-time algorithm for maximum-weight $b$-matching problem to obtain an $O(\sqrt{bn})$-approximation. When $b$ is constant and all lists have size $n - O(\sqrt{n})$, our guarantees asymptotically match the best known approximation factor for MaxQAP, yielding the first approximation algorithms for these two variants.

翻译：我们研究了最大二次分配问题（MaxQAP）两种自然推广的近似算法。在最大列表限制二次分配问题中，一个部分集合中的每个节点只能与预设列表中的节点匹配。对于节点数为$n$且每个列表大小至少为$n - O(\sqrt{n})$的实例，我们基于Makarychev、Manokaran和Sviridenko的线性规划松弛与随机舍入框架，设计了一个随机$O(\sqrt{n})$-近似算法。在最大二次$b$-匹配分配问题中，我们寻求最大化MaxQAP目标的$b$-匹配。我们改进了标准MaxQAP松弛方法，将$b$次独立迭代的随机舍入与最大权重$b$-匹配问题的多项式时间算法相结合，获得了$O(\sqrt{bn})$-近似结果。当$b$为常数且所有列表大小为$n - O(\sqrt{n})$时，我们的保证渐近匹配了MaxQAP已知的最佳近似因子，从而为这两种变体提供了首个近似算法。