{
  "id": "1709.08983",
  "version": "v1",
  "published": "2017-09-26T12:51:51.000Z",
  "updated": "2017-09-26T12:51:51.000Z",
  "title": "On Tropical Linear and Integer Programs",
  "authors": [
    "Peter Butkovic"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "We present simple compact proofs of the strong and weak duality theorems of tropical linear programming. It follows that there is no duality gap for a pair of tropical primal-dual problems. This result together with known properties of subeigenvectors enables us to directly solve a special tropical linear program with two-sided constraints. We also study the duality gap in tropical integer linear programming. A direct solution is available for the primal problem. An algorithm of quadratic complexity is presented for the dual problem. A direct solution is available provided that all coefficients of the objective function are integer. This solution yields a good estimate of the optimal objective function value in the general case.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-09-26T12:51:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "15A18",
      "15A80"
    ],
    "keywords": [
      "integer programs",
      "duality gap",
      "direct solution",
      "simple compact proofs",
      "special tropical linear program"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}