{
  "id": "2003.00855",
  "version": "v1",
  "published": "2020-03-02T13:07:37.000Z",
  "updated": "2020-03-02T13:07:37.000Z",
  "title": "Optimal transport: discretization and algorithms",
  "authors": [
    "Quentin Merigot",
    "Boris Thibert"
  ],
  "categories": [
    "math.NA",
    "cs.NA",
    "math.OC"
  ],
  "abstract": "This chapter describes techniques for the numerical resolution of optimal transport problems. We will consider several discretizations of these problems, and we will put a strong focus on the mathematical analysis of the algorithms to solve the discretized problems. We will describe in detail the following discretizations and corresponding algorithms: the assignment problem and Bertsekas auction's algorithm; the entropic regularization and Sinkhorn-Knopp's algorithm; semi-discrete optimal transport and Oliker-Prussner or damped Newton's algorithm, and finally semi-discrete entropic regularization. Our presentation highlights the similarity between these algorithms and their connection with the theory of Kantorovich duality.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-03-02T13:07:37.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "discretization",
      "bertsekas auctions algorithm",
      "optimal transport problems",
      "semi-discrete optimal transport",
      "semi-discrete entropic regularization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}