-1
$\begingroup$

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.

  • 0
    Whenever I take n/2 elements of x, they sum to at least 1...I hope things become clearer now?2012-10-22

1 Answers 1

0

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 ;(

  • 0
    Summation xi >=1 ???2012-10-22