-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
    Could you please clearly formulate what the conditions are on the $x_i, i, S$? And what have you tried to solve the problem?2012-10-22
  • 0
    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...2012-10-22
  • 0
    S are just the set of indices2012-10-22
  • 0
    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$?2012-10-22
  • 0
    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?2012-10-22
  • 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