Goemans, Michel (?)


Complexity of square-root sum ★★

Author(s): Goemans

\begin{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. $ \end{question}

Keywords: semi-definite programming

Syndicate content