1
$\begingroup$

Consider the following optimization problem: Let $n$ be even and let $c, x$ be positive vectors in $\mathbb{R}^n.$ Find $\min(c^Tx)$ for $\sum_S x_i\geq 1,$ for any $S\subset \{1,...,n\}$ with $|S| =n/2$. We have to show that the ellipsoid algorithm can be used to get a poly(n)-time algorithm for the problem.

  • 0
    @KevinCarlson ...I also think there is an O(nlogn) algorithm for the problem.But again can't figure out how ...2012-10-22

0 Answers 0