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.

  • 2
    $\begingroup$ For 1 and 2, search for maximum weight $b$-matching problem or degree-constrained subgraph problem. To add 3, maybe also include cardinality-constrained. $\endgroup$
    – RobPratt
    Commented Mar 27, 2020 at 2:51

1 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.

  • 1
    $\begingroup$ Thank you for your thoughts. The question is what bound can be proved for the solution to the (reformulated) integer programming. $\endgroup$
    – user306101
    Commented Mar 27, 2020 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.