2025/12/08 by Nanta, Jiratchaphat, Suppakitpaisarn, Vorapong, Sripratak, Piyashat
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2512.07618
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(√(n)), we design a randomized O(√(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(√(bn))-approximation. When b is constant and all lists have size n - O(√(n)), our guarantees asymptotically match the best known approximation factor for MaxQAP, yielding the first approximation algorithms for these two variants.