Optimization Online


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

Etienne De Klerk (e.deklerk***at***uvt.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society