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?

  • $\begingroup$ 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$. $\endgroup$ – alext87 Jun 12 '10 at 8:31

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.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.