Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP

This paper presents the first approximation algorithms for two generalizations of the Maximum Quadratic Assignment Problem—Maximum List-Restricted Quadratic Assignment and Maximum Quadratic $b$-Matching Assignment—achieving $O(\sqrt{n}+k)$ and $O(\sqrt{bn})$ approximation factors respectively, which asymptotically match the best known bounds for the standard MaxQAP under specific conditions.

The Gist

Imagine you are the manager of a massive, high-stakes dance competition. You have two groups of dancers: Group G (the performers) and Group H (the judges).

Your goal is to pair them up to create the most spectacular show possible. The "score" of the show depends on two things:

1. How well the performers get along with each other (their chemistry).
2. How well the judges get along with each other (their shared taste).

If you pair Performer A with Judge X, and Performer B with Judge Y, the total score is the sum of the chemistry between A and B multiplied by the shared taste between X and Y. You want to find the perfect pairing that maximizes this total score.

This is the Quadratic Assignment Problem (QAP). In the real world, this is like trying to arrange a factory floor so that machines that talk to each other often are placed close together, or arranging a seating chart for a wedding so that guests who get along sit near each other.

The problem is notoriously difficult. It's like trying to solve a Rubik's Cube that has billions of sides; checking every single possibility would take longer than the age of the universe. So, computer scientists use "Approximation Algorithms"—smart shortcuts that get you a very good solution quickly, even if it's not mathematically perfect.

This paper introduces two new, more realistic versions of this dance problem and offers new shortcuts to solve them.

The Two New Rules of the Dance

In the classic version of the problem, you can pair any performer with any judge. But in the real world, things are rarely that flexible. The authors looked at two specific constraints:

1. The "List-Restricted" Dance (The Picky Dancer)

Imagine some performers are shy. Performer A only wants to dance with Judges X, Y, or Z. They refuse to dance with anyone else.

• The Challenge: You can't just pair A with anyone; you have to respect their "list."
• The Paper's Solution: The authors created a smart algorithm that respects these lists. They proved that if every performer has a list of at least $n - k$ acceptable judges (where $n$ is the total number of judges and $k$ is a small number of "no-gos"), their algorithm can find a pairing that is almost as good as the perfect one.
• The Analogy: It's like organizing a speed dating event where everyone has a "do not date" list. The algorithm ensures you still get a great match, even if people are picky.

2. The "b-Matching" Dance (The Multi-Tasking Dancer)

In the classic problem, it's strictly one-on-one. But what if a performer is so popular they can dance with multiple judges at once? Or what if a judge is so busy they need to evaluate multiple performers?

• The Challenge: Instead of a 1-to-1 pairing, we are looking for a "b-matching," where each person can be paired with up to $b$ people. This makes the problem much more complex because the connections overlap.
• The Paper's Solution: The authors developed a method that runs the "perfect pairing" algorithm $b$ times in a row, layering the results together. They proved this creates a solution that is very close to the best possible outcome.
• The Analogy: Imagine a DJ who can spin records for multiple dance floors simultaneously. The algorithm helps figure out how to schedule the DJ's time across all floors to keep the party energy at its peak.

How the Magic Trick Works (The "Randomized Rounding")

How do these algorithms actually work? They use a clever technique called Randomized Rounding.

1. The Dream State (Linear Programming): First, the computer solves a simplified version of the problem where it allows "fractional" pairings. Instead of saying "Performer A is 100% with Judge X," it says "Performer A is 60% with Judge X and 40% with Judge Y." This is easy to calculate and gives a "Dream Score" (the best possible theoretical score).
2. The Reality Check (Rounding): You can't have a 60% dance. You need a real, solid pairing. The algorithm takes those fractions and uses a coin-flip method (randomness) to decide who actually dances with whom.
   • If the computer says "60% chance," it flips a weighted coin.
   • It does this in a very structured way, splitting the dancers into groups and ensuring the randomness doesn't ruin the overall score.

The authors refined this process to handle the "List-Restricted" and "b-Matching" rules. They proved that even with these extra rules, the "Dream Score" doesn't drop too far when you turn it into a real, solid pairing.

Why Does This Matter?

In the past, if you had a factory layout problem where some machines couldn't go near certain areas (List-Restricted) or where some machines needed to serve multiple stations (b-Matching), you had to use slow, guess-and-check methods that often failed.

This paper provides the first reliable, fast "shortcuts" for these specific, messy real-world scenarios.

• For the List-Restricted version: If your constraints aren't too crazy (you have plenty of options), the solution is nearly perfect.
• For the b-Matching version: Even if people have to juggle multiple partners, the solution stays very strong.

The Bottom Line

Think of this paper as a new, smarter rulebook for organizing complex events. Whether you are arranging a factory, matching students to projects, or aligning social networks, the authors have shown us how to get a "great" result quickly, even when the rules are strict or the connections are complicated. They didn't just solve the math; they proved that their shortcuts are the best we currently know how to do.

Technical Summary

Here is a detailed technical summary of the paper "Approximation Algorithms for the b-Matching and List-Restricted Variants of MaxQAP".

1. Problem Definition

The paper addresses two natural generalizations of the Maximum Quadratic Assignment Problem (MaxQAP).

• Standard MaxQAP: Given two weighted graphs $G$ and $H$ with $n$ nodes each, find a bijection $\pi: V_G \to V_H$ that maximizes the sum of products of edge weights: $\sum_{u,v} w_G(u,v) w_H(\pi(u), \pi(v))$.
• List-Restricted MaxQAP: A variant where each node $u \in V_G$ can only be mapped to a node in a prescribed subset (list) $L(u) \subseteq V_H$. The goal is to find a compatible matching maximizing the same quadratic objective. The paper assumes the list size is large, specifically $|L(u)| \ge n - k$ for some parameter $k$.
• Maximum Quadratic b-Matching Assignment Problem (MaxQbAP): A variant where the bijection constraint is relaxed to a b-matching. Each node in $V_G$ can be matched to up to $b$ nodes in $V_H$ (and vice versa). The objective remains maximizing the quadratic sum of matched edge weights.

The authors note that while MaxQAP is NP-hard and has an existing $O(\sqrt{n})$ approximation, no theoretical approximation algorithms existed for these specific constrained variants prior to this work.

2. Methodology

The core methodology relies on Linear Programming (LP) relaxation combined with Randomized Rounding, extending the framework established by Makarychev, Manokaran, and Sviridenko (2014) for standard MaxQAP.

A. List-Restricted MaxQAP

• LP Formulation: The authors modify the standard MaxQAP LP relaxation (Adams and Johnson formulation) by adding constraints $x_{up} = 0$ if $p \notin L(u)$.
• Algorithm (Algorithm 1):
  1. Solve the relaxed LP to obtain fractional values $x^*_{up}$ and $y^*_{upvq}$.
  2. Randomly partition $V_G$ and $V_H$ into two sets each: Left ($G_L, H_L$) and Right ($G_R, H_R$).
  3. Left Side Matching ($M_L$): Nodes in $H_L$ probabilistically choose neighbors in $G_L$ based on LP values. Conflicts are resolved by randomly selecting one edge per node.
  4. Right Side Matching ($M_R$): Construct a weight function $w(v, q)$ for nodes in $G_R \times H_R$ based on the edges selected in $M_L$. Compute a maximum-weight compatible matching on the right side.
• Analysis Strategy: The objective value is split into a "heavy" part (edges involving the top $\approx \sqrt{n}$ weight neighbors) and a "light" part.
  • To handle the list restriction, the set of "heavy" neighbors $W_p$ is expanded to size $\lceil (\sqrt{n} + k^2 + k)/2 \rceil$.
  • Even if up to $k$ top choices are excluded by the list constraints, enough candidates remain to ensure the rounding captures a constant fraction of the LP optimum relative to the list size.

B. MaxQbAP (b-Matching Variant)

• LP Formulation: The capacity constraints in the LP are adjusted from $\sum x_{up} = 1$ to $\sum x_{up} \le b$.
• Algorithm (Algorithm 2):
  1. Solve the relaxed LP.
  2. Perform $b$ independent iterations of the randomized rounding process used in the standard MaxQAP.
  3. In each iteration $i$, generate a matching $M^{(i)}_L$ on the left partition and a random matching on the right.
  4. Combine the results: The final left matching is the union $\bigcup M^{(i)}_L$. The right side matching is computed as a maximum-weight b-matching based on the weights induced by the left side.
• Analysis Strategy:
  • The analysis leverages the fact that a $b$-matching can be decomposed into $b$ disjoint matchings.
  • By running $b$ independent rounds, the probability of capturing edges increases.
  • The authors refine the analysis to show that the approximation factor is not simply $O(b\sqrt{n})$ (which would be the naive bound), but improves to $O(\sqrt{bn})$. This is achieved by carefully analyzing the probability that edges are selected across the $b$ independent rounds and the interaction between the heavy and light parts of the objective function.

3. Key Contributions

1. Formalization: The paper formally defines and unifies the List-Restricted and b-Matching variants of MaxQAP, establishing the first theoretical framework for these problems.
2. List-Restricted Approximation: Developed an $O(\sqrt{n} + k)$-approximation algorithm. When $k = O(\sqrt{n})$, this matches the best-known $O(\sqrt{n})$ ratio for standard MaxQAP.
3. b-Matching Approximation: Developed an $O(\sqrt{bn})$-approximation algorithm. When $b$ is constant, this also matches the $O(\sqrt{n})$ bound of the standard problem.
4. Technical Refinement:
   • Introduced a modified LP relaxation and a specific expansion of the "heavy" neighbor set to handle list constraints.
   • Refined the randomized rounding analysis for the b-matching case to achieve a $\sqrt{b}$ improvement over the naive $b$-factor, utilizing independent iterations and maximum-weight b-matching solvers.
5. Relationship Proof: Proved that an $\alpha$-approximation for a simplified "duplicate" version of the b-matching problem (dup-MaxQbAP) implies a $2\alpha$-approximation for the original MaxQbAP, allowing the authors to focus on the easier-to-analyze variant.

4. Results

• Approximation Ratios:
  • List-Restricted MaxQAP: $O(\sqrt{n} + k)$.
  • MaxQbAP: $O(\sqrt{bn})$.
• Asymptotic Optimality: For cases where the list restrictions are mild ($k = O(\sqrt{n})$) or $b$ is a small constant, the proposed algorithms achieve the same asymptotic approximation ratio as the best-known algorithm for the unconstrained MaxQAP.
• Computational Complexity: Both algorithms run in polynomial time, relying on solving LPs and standard maximum-weight matching/b-matching algorithms.

5. Significance

• Theoretical Gap Filling: Prior to this work, there were no known approximation algorithms for MaxQAP under list restrictions or b-matching constraints. This paper initiates the approximation-theoretic study of these variants.
• Practical Relevance: The constraints modeled (list restrictions and capacity limits) are highly relevant to real-world applications such as:
  • Pattern Recognition/Computer Vision: Where landmarks in images can only match specific regions (list restriction).
  • Network Alignment: Where node attributes restrict valid mappings.
  • Quantum Circuit Placement: Where hardware architecture forbids certain qubit mappings.
  • Robustness: The b-matching variant allows for matching nodes with limited capacities or handling noisy data where strict one-to-one correspondence is too rigid.
• Methodological Impact: The techniques used (refined LP rounding, handling list constraints via set expansion, and iterative b-matching decomposition) provide a blueprint for tackling other constrained quadratic assignment problems.

In conclusion, the paper successfully extends the state-of-the-art in MaxQAP approximation to constrained settings, proving that these natural generalizations can be approximated with ratios comparable to the unconstrained problem under reasonable parameter assumptions.