Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP
Authors
Jiratchaphat Nanta
Vorapong Suppakitpaisarn
Piyashat Sripratak
Abstract
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.
