The Complexity of Optimizing over a Simplex, Hypercube or Sphere: A Short Survey

Research output: Working paperDiscussion paperOther research output

390 Downloads (Pure)

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.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages13
Volume2006-85
Publication statusPublished - 2006

Publication series

NameCentER Discussion Paper
Volume2006-85

Keywords

  • computational complexity
  • global optimization
  • linear and semidefinite programming
  • approximation algorithms

Fingerprint Dive into the research topics of 'The Complexity of Optimizing over a Simplex, Hypercube or Sphere: A Short Survey'. Together they form a unique fingerprint.

  • Cite this

    de Klerk, E. (2006). The Complexity of Optimizing over a Simplex, Hypercube or Sphere: A Short Survey. (CentER Discussion Paper; Vol. 2006-85). Operations research.