On the complexity of computing the diameter of a polytope
On the complexity of computing the diameter of a polytope
复制标题
关于计算多胞形直径的复杂性
作者：
A. Frieze;S. Teng
本文证明了由线性不等式所确定的多面体的组合直径是DP-困难的。我们的结果部分解决了一个长期悬而未决的问题。
We show that it isDP-hard to determine the combinatorial diameter of a polytope specified by linear inequalities with integer data. Our result partially resolves a long-term open question.