Oracle-polynomial-time approximation of largest simplices in convex bodies
Zeitschrift:
Discrete Mathematics
Jahrgang:
221
Jahr:
2000
Seiten von - bis:
79-92
Sprache:
Englisch
Stichwörter:
Simplex Determinant Algorithmic theory of convex bodies Approximation Oracle Polynomial time
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.