Polynomial-time approximation of largest simplices in V-polytopes

✍ Scribed by Asa Packer

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 324 KB
• Volume: 134
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00226-9

✦ Synopsis

This paper considers the problem of computing the squared volume of a largest j-dimensional simplex in an arbitrary d-dimensional polytope P given by its vertices (a "V -polytope"), for arbitrary integers j and d with 1 6 j 6 d. The problem was shown by Gritzmann, Klee and Larman to be NP-hard. This paper examines the possible accuracy of deterministic polynomial-time approximation algorithms for the problem. On the negative side, it is shown that unless P = NP, no such algorithm can approximately solve the problem within a factor of less than 1.09. It is also shown that the NP-hardness and inapproximability continue to hold when the polytope P is restricted to be an a ne crosspolytope.

On the positive side, a simple deterministic polynomial-time approximation algorithm for the problem is described. The algorithm takes as input integers j and d with 1 6 j 6 d and a V -polytope P of dimension d. It returns a j-simplex S ⊂ P such that vol 2 (T ) vol 2 (S) 6 A(Bj) j ;

where T is any largest j-simplex in P, and A and B are positive constants independent of j; d; P.