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.
using the ellipsoid algorithm to find a poly time algorithm for the optimization problem
1
$\begingroup$
linear-programming
convex-optimization
-
1I tried to edit your question, but I can't really see what you mean to say about the sets $S$. – 2012-10-22
-
0yeah thanks for the editing.S are just the set of indices – 2012-10-22
-
0also S is a subset of [n] not belongs to...[n] represents the set of n linearly independent columns – 2012-10-22
-
0Do you mean that whenever I take $n/2$ elements of $x$, they sum to at least $1$? – 2012-10-22
-
0yeah...right...xi's are elements of x.So x1,x2...xn/2 – 2012-10-22
-
0@KevinCarlson ...I also think there is an O(nlogn) algorithm for the problem.But again can't figure out how ... – 2012-10-22