Oracle-polynomial-time approximation of largest simplices in convex bodies

Andreas Brieden, Peter Gritzmann, Victor Klee

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

With focus on the case of variable dimension n, this paper is concerned with deterministic polynomial-time approximation of the maximum j-measure of j-simplices contained in a given n-dimensional convex body K. Under the assumption that K is accessible only by means of a weak separation oracle, upper and lower bounds on the accuracy of oracle-polynomial-time approximations are obtained.

Original languageEnglish
Pages (from-to)79-92
Number of pages14
JournalDiscrete Mathematics
Volume221
Issue number1-3
DOIs
StatePublished - 28 Jun 2000

Keywords

  • Algorithmic theory of convex bodies
  • Approximation
  • Determinant
  • Oracle
  • Polynomial time
  • Simplex

Fingerprint

Dive into the research topics of 'Oracle-polynomial-time approximation of largest simplices in convex bodies'. Together they form a unique fingerprint.

Cite this