I am thinking about this problem: Given $\beta_1,\beta_2,\ldots,\beta_n \in \mathbb{R}$, where $n$ is very large. Denote the sum of them by $S=\sum_{i=1}^n \beta_i$. For a fixed real number $\mu \in (0,1)$, consider the following optimization problem: $$ \Omega^{*}= { \underset{\Omega \subseteq \left\{1,2,\ldots,n\right\}}{{\arg\min} \, f(\Omega)} =\ |\mu S-\sum_{j \in \Omega}\beta_j|} $$ It is obviously an NP-hard problem, I wonder if there exists an algorithm that achieves an $O(n^\alpha)$ complexity and outputs a solution very close to the optimal solution. I am also interested with any prior results related to this problem.
Asked
Active
Viewed 25 times
