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.