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

Etienne De Klerk (e.deklerkuvt.nl)

Abstract: 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.

Keywords: computational complexity, global optimization, linear and semidefinite programming, approximation algorithms

Category 1: Global Optimization

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Nonlinear Optimization

Citation: CentER Discussion paper 2006-85 Tilburg University THe Netherlands

Download: [PDF]

Entry Submitted: 09/28/2006
Entry Accepted: 09/28/2006
Entry Last Modified: 10/04/2007

Modify/Update this entry