{
  "id": "2307.05246",
  "version": "v1",
  "published": "2023-07-11T13:21:59.000Z",
  "updated": "2023-07-11T13:21:59.000Z",
  "title": "Polytope Extensions with Linear Diameters",
  "authors": [
    "Volker Kaibel",
    "Kirill Kukharenko"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We describe constructions of extended formulations that establish a certain relaxed version of the Hirsch-conjecture and prove that if there is a pivot rule for the simplex algorithm for which one can bound the number of steps by the (monotone) diameter of the polyhedron of feasible solutions then the general linear programming problem can be solved in strongly polynomial time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-07-11T13:21:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52Bxx",
      "90C05"
    ],
    "keywords": [
      "polytope extensions",
      "linear diameters",
      "general linear programming problem",
      "simplex algorithm",
      "pivot rule"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}