Goemans, Michel (?)


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

Syndicate content