Skip to main content
MathOverflow

Return to Question

$k-$ -> $k$-; [reference-request]; deleted "thanks"
Source Link
LSpice
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Finding the best $ka $k$-$subsetsubset which maximizes a matrix sum

Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem:

Is there a polynomial-time solution to the following problem: $$S^\star = \arg\max_{S\subset [N]:\\ |S|\le k} \sum_{i,j\in S}M_{ij}.$$$$S^\star = \arg\max_{\substack{S\subset [N]:\\ |S|\le k}} \sum_{i,j\in S}M_{ij}?$$

This seems to be hard in general (that is, it requires exponential time-complexity), but I could not find a direct link to any known problem. I first thought that this problem is related to the maximum subset problem, but I am not sure. It will be really helpful if somebody can provide any reference to any related problem. It seems that approximate solutions can be found for this problem, but I was unable to find that too after a Google search. It will be really great if someone can give any reference. Thanks in advance.

Finding the best $k-$subset which maximizes a matrix sum

Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem:

Is there a polynomial-time solution to the following problem: $$S^\star = \arg\max_{S\subset [N]:\\ |S|\le k} \sum_{i,j\in S}M_{ij}.$$

This seems to be hard in general (that is, it requires exponential time-complexity), but I could not find a direct link to any known problem. I first thought that this problem is related to the maximum subset problem, but I am not sure. It will be really helpful if somebody can provide any reference to any related problem. It seems that approximate solutions can be found for this problem, but I was unable to find that too after a Google search. It will be really great if someone can give any reference. Thanks in advance.

Finding a $k$-subset which maximizes a matrix sum

Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem:

Is there a polynomial-time solution to the following problem: $$S^\star = \arg\max_{\substack{S\subset [N]:\\ |S|\le k}} \sum_{i,j\in S}M_{ij}?$$

This seems to be hard in general (that is, it requires exponential time-complexity), but I could not find a direct link to any known problem. I first thought that this problem is related to the maximum subset problem, but I am not sure. It will be really helpful if somebody can provide any reference to any related problem. It seems that approximate solutions can be found for this problem, but I was unable to find that too after a Google search. It will be really great if someone can give any reference.

Source Link
Samrat Mukhopadhyay
Samrat Mukhopadhyay
  • 554
  • 3
  • 13

Finding the best $k-$subset which maximizes a matrix sum

Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem:

Is there a polynomial-time solution to the following problem: $$S^\star = \arg\max_{S\subset [N]:\\ |S|\le k} \sum_{i,j\in S}M_{ij}.$$

This seems to be hard in general (that is, it requires exponential time-complexity), but I could not find a direct link to any known problem. I first thought that this problem is related to the maximum subset problem, but I am not sure. It will be really helpful if somebody can provide any reference to any related problem. It seems that approximate solutions can be found for this problem, but I was unable to find that too after a Google search. It will be really great if someone can give any reference. Thanks in advance.