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 language | English |
---|---|
Pages (from-to) | 79-92 |
Number of pages | 14 |
Journal | Discrete Mathematics |
Volume | 221 |
Issue number | 1-3 |
DOIs | |
State | Published - 28 Jun 2000 |
Keywords
- Algorithmic theory of convex bodies
- Approximation
- Determinant
- Oracle
- Polynomial time
- Simplex