Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there is a feasible solution that is $k$-sparse, i.e. there are only $k$-nonzero elements in $x$?

What about if we know an upper bound on the $L_1$-norm of the solution $|x|_1\le B$. Would it be possible to answer the system has a sparse solution in polynomial time?

P.S. I'm aware of this question, but the answer does not address whether this approach always finds a feasible solution in polynomial time.


Your Answer

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

Browse other questions tagged or ask your own question.