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. 



approximate diameter of polytopes in high dimensions
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](http://link.springer.com/article/10.1007/s00454-002-2756-x#page-1).)
> 
> 
> 


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](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=743451).)
> 
> 
> 


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.


