Maximum weight b-matching with global cardinality constraint

Question

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.

Answer 1

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.