{
  "id": "2104.09488",
  "version": "v1",
  "published": "2021-04-19T17:46:51.000Z",
  "updated": "2021-04-19T17:46:51.000Z",
  "title": "Monge solutions and uniqueness in multi-marginal optimal transport via graph theory",
  "authors": [
    "Brendan Pass",
    "Adolfo Vargas-Jiménez"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "We study a multi-marginal optimal transport problem with surplus $b(x_{1}, \\ldots, x_{m})=\\sum_{\\{i,j\\}\\in P} x_{i}\\cdot x_{j}$, where $P\\subseteq Q:=\\{\\{i,j\\}: i, j \\in \\{1,2,...m\\}, i \\neq j\\}$. We reformulate this problem by associating each surplus of this type with a graph with $m$ vertices whose set of edges is indexed by $P$. We then establish uniqueness and Monge solution results for two general classes of surplus functions. Among many other examples, these classes encapsulate the Gangbo and \\'{S}wi\\c{e}ch surplus [12] and the surplus $\\sum_{i=1}^{m-1}x_{i}\\cdot x_{i+1} + x_{m}\\cdot x_{1}$ studied in an earlier work by the present authors [23].",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-04-19T17:46:51.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "graph theory",
      "uniqueness",
      "multi-marginal optimal transport problem",
      "monge solution results",
      "earlier work"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}