{
  "id": "1809.06780",
  "version": "v1",
  "published": "2018-09-07T14:50:39.000Z",
  "updated": "2018-09-07T14:50:39.000Z",
  "title": "On the diameter of polytope",
  "authors": [
    "Yaguang Yang"
  ],
  "comment": "6 pages",
  "categories": [
    "math.MG",
    "math.CO",
    "math.OC"
  ],
  "abstract": "Bonifas et. al. \\cite{bsehn14} derived an upper bound of a polytope $P=\\{ x\\in \\mathbb{R}^n: Ax \\le b \\}$ where $A \\in \\mathbb{Z}^{m \\times n}$ and $m>n$. This comment indicates that their method can be applied to the case where $A \\in \\mathbb{R}^{m \\times n}$, which results in an upper bound of the diameter for the general polytope $\\mathcal{O} \\left( \\frac{n^3 \\Delta}{\\det(A^*)} \\right)$, where $\\Delta$ is the largest absolute value among all $(n-1) \\times (n-1)$ sub-determinants of $A$ and ${\\det(A^*)}$ is the smallest absolute value among all nonzero $n \\times n$ sub-determinants of $A$. For each given polytope, since $\\Delta$ and $\\det(A^*)$ are fixed, the diameter is bounded by $\\mathcal{O}(n^3)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-09-07T14:50:39.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "upper bound",
      "smallest absolute value",
      "largest absolute value",
      "sub-determinants",
      "general polytope"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}