# Finding an $O(n \log n)$ time algorithm for an optimization problem

Consider the following optimization problem:

Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ |S| = n/2: \sum_{i \in S} x_i \geq 1\right)\right\}.$$

I would like to find an $O(n \log n)$ time algorithm for the problem.

-
Could you please clearly formulate what the conditions are on the $x_i, i, S$? And what have you tried to solve the problem? –  TMM Oct 22 '12 at 9:45
see I dont know how to write this out...a) summation xi>=1 for i belongs to S ... b)S belongs to [n] with |S|=n/2 I was thinking of the number of steps in the problem ...for this it is (n choose (n/2)) and then in some way decrease the number of steps... –  elnino Oct 22 '12 at 9:59
S are just the set of indices –  elnino Oct 22 '12 at 10:00
If you cannot clearly phrase the question, how do you expect us to clearly answer it? What are you taking the minimum over? What are the conditions on $x$? –  TMM Oct 22 '12 at 10:25
The minimum is taken over all c(transpose)*x and x in this case is {x1,x2,x3...,xi} for i taken from S...Is it clear now? –  elnino Oct 22 '12 at 10:48
show 1 more comment

I don't mean to be thick here, but if $c > 0$, and $x \geq 0$ ... isn't the minimum then just $x = [0\ 0\ ...\ 0]^T$? What do you need the algorithm for then? Sorry if I am overlooking anything ;(