{"ID":2831729,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.07618","arxiv_id":"2512.07618","title":"Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP","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 - k$, we design a randomized $O(\\sqrt{n}+k)$-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.","short_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 l...","url_abs":"https://arxiv.org/abs/2512.07618","url_pdf":"https://arxiv.org/pdf/2512.07618v2","authors":"[\"Jiratchaphat Nanta\",\"Vorapong Suppakitpaisarn\",\"Piyashat Sripratak\"]","published":"2025-12-08T15:06:28Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}