1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the useful answer and references. I will try to work on s hypothesis on Q and a restriction on the polytopes to make the question more interesting. $\endgroup$ – rjm Sep 2 '15 at 6:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.