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. This is because its constraint matrix is totally unimodular. However, adding condition 3 will break it, hence necessitating an approximate solution. Any idea with a provable bound will be appreciated.

Thank you.

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.