Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I tried to edit your question, but I can't really see what you mean to say about the sets $S$. – Kevin Carlson Oct 22 '12 at 10:42
yeah thanks for the editing.S are just the set of indices – elnino Oct 22 '12 at 10:49
also S is a subset of [n] not belongs to...[n] represents the set of n linearly independent columns – elnino Oct 22 '12 at 10:52
Do you mean that whenever I take $n/2$ elements of $x$, they sum to at least $1$? – Kevin Carlson Oct 22 '12 at 11:04
yeah...right...xi's are elements of x.So x1,x2...xn/2 – elnino Oct 22 '12 at 11:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.