{
  "id": "1308.0454",
  "version": "v2",
  "published": "2013-08-02T10:10:52.000Z",
  "updated": "2014-12-21T16:29:52.000Z",
  "title": "Tropicalizing the simplex algorithm",
  "authors": [
    "Xavier Allamigeon",
    "Pascal Benchimol",
    "Stéphane Gaubert",
    "Michael Joswig"
  ],
  "comment": "v1: 35 pages, 7 figures, 4 algorithms; v2: improved presentation, 39 pages, 9 figures, 4 algorithms",
  "categories": [
    "math.CO",
    "math.OC"
  ],
  "abstract": "We develop a tropical analog of the simplex algorithm for linear programming. In particular, we obtain a combinatorial algorithm to perform one tropical pivoting step, including the computation of reduced costs, in O(n(m+n)) time, where m is the number of constraints and n is the dimension.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-08-02T10:10:52.000Z",
      "comment": "35 pages, 7 figures, 4 algorithms",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-12-21T16:29:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "14T50",
      "90C05"
    ],
    "keywords": [
      "simplex algorithm",
      "tropicalizing",
      "combinatorial algorithm",
      "tropical analog"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 35,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1308.0454A"
    }
  }
}