The Complexity of Optimizing over a Simplex, Hypercube or Sphere

A Short Survey

Research output: Working paperDiscussion paperOther research output

324 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

Fingerprint

Hypercube
Inapproximability
Continuous Function
Computational Complexity
Optimization Problem
Approximation
Review
Class

Keywords

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

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). Tilburg: Operations research.
de Klerk, E. / The Complexity of Optimizing over a Simplex, Hypercube or Sphere : A Short Survey. Tilburg : Operations research, 2006. (CentER Discussion Paper).
@techreport{88640b6d5240472d8669446b519929ed,
title = "The Complexity of Optimizing over a Simplex, Hypercube or Sphere: A Short Survey",
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",
author = "{de Klerk}, E.",
note = "Subsequently published in the European Journal for Operations Research and Economics, 2008 Pagination: 13",
year = "2006",
language = "English",
volume = "2006-85",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

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, Tilburg.

The Complexity of Optimizing over a Simplex, Hypercube or Sphere : A Short Survey. / de Klerk, E.

Tilburg : Operations research, 2006. (CentER Discussion Paper; Vol. 2006-85).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - The Complexity of Optimizing over a Simplex, Hypercube or Sphere

T2 - A Short Survey

AU - de Klerk, E.

N1 - Subsequently published in the European Journal for Operations Research and Economics, 2008 Pagination: 13

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - computational complexity

KW - global optimization

KW - linear and semidefinite programming

KW - approximation algorithms

M3 - Discussion paper

VL - 2006-85

T3 - CentER Discussion Paper

BT - The Complexity of Optimizing over a Simplex, Hypercube or Sphere

PB - Operations research

CY - Tilburg

ER -

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