semi-definite programming

Theoretical Comp. Sci. » Complexity

Complexity of square-root sum ★★

Author(s): Goemans

Question What is the complexity of the following problem?

Given $a_1,\dots,a_n; k$ , determine whether or not $\sum_i \sqrt{a_i} \leq k.$

Keywords: semi-definite programming

Posted by abie
updated July 1st, 2011