The problem is NP-hard, unless there is more to it than what is stated, and one cannot hope for an efficient approximation to any reasonable degree unless P = NP.
One way to show this is by a reduction from vertex cover, which may be established as follows. For any undirected graph $G = (V,E)$, let $Minmathbb{R}^{Etimes V}$ be the incidence matrix of $G$, and let $K$ be the cone of vectors $xinmathbb{R}^V$ such that $Mx geq 0$ (or $-Mx leq 0$, as the question statement would prefer). If $G$ has a vertex cover of size $k$, then $inf_{xin K} F_{k+1}(x) = -infty$. If not, $inf_{xin K} F_{k+1}(x) = 0$. Without further assumptions, this would seem to rule out the existence of an efficient approximation algorithm of any sort.
The same general idea, with simple modifications, will establish a reduction if $x$ is constrained to the nonnegative orthant.
It should also be noted that the problem does not become easier under the assumption $xinmathbb{Z}^n$, counter to what the question suggests.
No comments:
Post a Comment