The complexity of optimizing over a simplex, hypercube or sphere: a short survey
Etienne de Klerk · Central European Journal of Operations Research · 2007
We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere. These relatively simple optimization problems arise naturally from diverse applications. We review known approximation results as well as negative (inapproximability) results from the recent literature.