Let $F_k(X)$ denote the k-th largest element of vector $X$. The problem is:
Minimize $F_k(X)$
Subject to: $AX<=b$
Note that if X belongs to $Z^{n}$. Then this problem is called combinatorial optimization and has polynomial solution. However, if X belongs to $R^{n}$, things become not clear.
I am wondering if there exists any effective algorithm to solve this problem. Or is this NP-Complete? If it is NP-Complete, is there any good approximation?
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 $M\in\mathbb{R}^{E\times V}$ be the incidence matrix of $G$, and let $K$ be the cone of vectors $x\in\mathbb{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_{x\in K} F_{k+1}(x) = -\infty$. If not, $\inf_{x\in 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 $x\in\mathbb{Z}^n$, counter to what the question suggests.
