Home » Subject » Theoretical Comp. Sci. » Complexity
Importance: Medium ✭✭
Author(s): Goemans, Michel (?)
Subject: Theoretical Computer Science
» Complexity
Keywords: semi-definite programming
Recomm. for undergrads: no
Posted by: abie
on: July 18th, 2007
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. $

As of a 1998 survey, the complexity of this problem was unknown. I'm not sure if that's still the case. But I wanted to see how easy it was to make a page about it.

This is the key to determining if semi-definite programming is truly solvable in polynomial time (it can be approximated to within $ \varepsilon $ using the interior point method or the ellipsoid algorithm in time polynomial in the size of the instance and $ \log 1/\varepsilon $.

Bibliography

[G] Michal Goemans, Semidefinite Programming and Combinatorial Optimization


* indicates original appearance(s) of problem.
5 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options