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$ 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.

share|cite|improve this question
Could you please clearly formulate what the conditions are on the $x_i, i, S$? And what have you tried to solve the problem? – TMM Oct 22 '12 at 9:45
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... – elnino Oct 22 '12 at 9:59
S are just the set of indices – elnino Oct 22 '12 at 10:00
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$? – TMM Oct 22 '12 at 10:25
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? – elnino Oct 22 '12 at 10:48

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

share|cite|improve this answer
Summation xi >=1 ??? – elnino Oct 22 '12 at 13:22

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.