Take the 2-minute tour ×

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?

share|improve this question
Since the $k^{th}$ element of the vector $X$ is not well-defined - there are possibly more than one. To pose this question better $F_k(X)$ should denote the magnitude of the $k^{th}$ largest element in $X$. –  alext87 Jun 12 '10 at 8:31

1 Answer 1

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.

share|improve this answer

Your Answer


