1
$\begingroup$

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.

$\endgroup$

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.