6
$\begingroup$

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.

$\endgroup$
  • 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 Mar 27 at 2:51
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 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 Mar 27 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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