{
  "id": "math/0301076",
  "version": "v1",
  "published": "2003-01-09T10:09:10.000Z",
  "updated": "2003-01-09T10:09:10.000Z",
  "title": "The Random Edge Rule on Three-Dimensional Linear Programs",
  "authors": [
    "Volker Kaibel",
    "Raphael Mechtel",
    "Micha Sharir",
    "Günter M. Ziegler"
  ],
  "comment": "21 pages (10 pages extended abstract + 11 pages appendix)",
  "categories": [
    "math.CO",
    "math.OC"
  ],
  "abstract": "The worst-case expected length f(n) of the path taken by the simplex algorithm with the Random Edge pivot rule on a 3-dimensional linear program with n constraints is shown to be bounded by 1.3445 n <= f(n) <= 1.4943 n for large enough n.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2003-01-09T10:09:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C05",
      "52B10",
      "68W20"
    ],
    "keywords": [
      "three-dimensional linear programs",
      "random edge rule",
      "random edge pivot rule",
      "path taken",
      "simplex algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003math......1076K"
    }
  }
}