Open Problem Garden

recreational mathematics

Goemans, Michel (?)

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

semi-definite programming

graceful labeling

combinatorics

locally testable

coding

robustness

codes