The complexity of optimizing over a simplex, hypercube or sphere: a short survey

We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere. These relatively simple optimization problems have many applications. We review known approximation results as well as negative (inapproximability) results from the recent literature.

Citation

CentER Discussion paper 2006-85 Tilburg University THe Netherlands

Article

Download

View PDF