# Maximum weight b-matching with global cardinality constraint

Suppose $$A$$ is an $$n$$-by-$$n$$ symmetric matrix whose entries are all nonnegative. $$A_{ii} = 0$$ for all $$i$$. We want to find an $$n$$-by-$$n$$ binary ($$0/1$$ valued) matrix $$X$$ that maximizes

$$\sum_{ij} A_{ij} X_{ij}$$

under the constraints that

1. $$X$$ is symmetric ($$X^\top = X$$);
2. Each row of $$X$$ can have at most $$k$$ ones (the rest being zero);
3. The total number of $$1$$ in $$X$$ is at most $$m$$.

Here $$k \le n$$ and $$m \le n^2$$. I can think of a dynamic programming solution if 2 and 3 are the only conditions. But the symmetry in condition 1 makes it much harder. Does there exist a polynomial algorithm which can achieve multiplicatively constant approximation bound (under conditions 1, 2, 3)? Ideally the constant is universal, not dependent on $$n$$, $$k$$, or $$m$$.

If not, is there any hope for the combination of conditions 1 and 2? The combination of 1 and 3 is trivial to handle.

Edit: Conditions 1+2 lead to a maximum weight b-matching problem, which is solvable in polynomial time. Adding condition 3, however, still makes the problem hard, necessitating an approximate solution. Any idea with a provable bound will be appreciated.

Thank you.

• For 1 and 2, search for maximum weight $b$-matching problem or degree-constrained subgraph problem. To add 3, maybe also include cardinality-constrained. Mar 27 '20 at 2:51

If I understand the question correctly, both $$A$$ and $$X$$ matrices are symmetric. If so, you can simply ignore the lower half(or upper half) of both matrices because in your solution you should always have $$x_{ij}=x_{ji}$$ in addition it's known that $$a_{ij}=a_{ji}$$ (from symmetry of $$A$$ matrix). Solve the problem using the following integer programming:
\begin{align}\max&\quad Z/2=\sum_{i=1}^n\sum_{j=1}^n a_{ij}x_{ij} \\ \text{s.t.}&\quad\sum_{i=1}^n x_{ij}\le k \quad \forall j \in \{1,\ldots, n\} \\ &\quad\sum_{j=1}^n x_{ij}\le k \quad\forall i \in \{1,\ldots, n\} \\ &\quad\sum_{i=1}^n\sum_{j=1}^n x_{ij}\le m \\ &\quad x_{ij}\in \{0,1\}\end{align} As we only considered half of the matrices, the value of objective function should be multiplied by two. In other words $$Z$$ will be your final objective function.