approximate diameter of polytopes in high dimensions

Question

I just came across the following problem: Let us consider the unit corner of the n-cube $$ \Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 \mbox{ for all } i\right\}. $$ Let $P$ be a polytope in $\Delta_c^n$ generated as the intersection of $m$ half-spaces. Let us equip $\Delta^n$ with the distance defined with a positive-definite matrix $Q$. I am looking to compute the diameter of the set $P$.

From a quick exploration, the diameter is the maximal distance between two extremal points of $P$.

The problem is that the number of these extremal points is typically exponential in $n$.

But if $Q$ has only a few eigenvalues that are not small, is there a smart way to approximate the diameter of $P$ ?

I am interested in any setting, even randomized ones, where the diameter can be approximated correctly numerically. The only hypothesis I do like to keep is the fact that $n$ being large.

Answer 1

This is not a definitive answer.

For the Euclidean distance, it is NP-hard to approximate the diameter within a constant. The best that can be achieved is a factor of $O(\sqrt{n/\log n})$:

Brieden, Andreas. "Geometric optimization problems likely not contained in APX." Discrete and Computational Geometry 28, no. 2 (2002): 201-209. (Springer link.)

See the paper with the discouraging title, "Approximation of diameters: Randomization doesn’t help":

Brieden, Andreas, Peter Gritzman, Ravi Kannan, Victor Klee, László Lovász, and Miklós Simonovits. "Approximation of diameters: Randomization doesn't help." In IEEE Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998. pp. 244-251. IEEE, 1998. (IEEE link.)

So if there is any hope for your question, it will depend on the structure of the "positive-definite matrix $Q$," or on restrictions on the shape of the polytope, how it is formed as the intersection of specific halfspaces.