Is there a way to solve or approximate the concave program with separable objective? I would like to solve the following problem:
"minimize $\sum_{i=1}^k \sqrt{x_i}$ subject to some polytope constaints."
Is there a polynomial time algorithm to solve or approximate it?
Thanks.

Jian.
I special cases of this problem are a convex optimization problem. If x_i>0, then the objective is a posynomial. If the polytope can be described using posynomials, then the problem becomes a convex optimization problem. 

See the tutorial at http://www.stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf which discusses geometric programming and search for posynomial. 

--clarification-- 

See page 73 of the above link.

If your polytope can be described by a posynomial, then you can solve the polytope as a convex programming problem, by converting the problem into an equivalent form.

    Given:
      Minimize f0(x)
      s.t.
      fi(x)&lt;=0 for all i
      fj(x)=0 for all j


Where f0(x) is your original objective and fi(x) is your polytope. 

Let x_k an element in x be equal to exp(y_k).
Now, an equivalent problem is cast as:

      Minimize log(f0(exp(y))
      s.t.
      log(fi(exp(y))&lt;=0 for all i
      log(fj(exp(y))=0 for all j


The restriction here is that the only a subset of all polytopes will work in this formulation. However if you can find a reasonable approximation where the polytope is approximated by a set of posynomial constraints, then you will have a computationally fast solution. 

--- additional comments ----

The only other approach which might be faster than solving the primal problem is to use KKT conditions to as implied by Ashwinkumar. You can try solving the dual formed from the KKT conditions. Depending on the structure of the polytope, you might be able to find the answer faster.

See http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions.