{
  "id": "2408.14256",
  "version": "v1",
  "published": "2024-08-26T13:20:56.000Z",
  "updated": "2024-08-26T13:20:56.000Z",
  "title": "Looking for all solutions of the Max Atom Problem (MAP)",
  "authors": [
    "Laurent Truffet"
  ],
  "comment": "in French language",
  "categories": [
    "math.CO"
  ],
  "abstract": "This present paper provides the absolutely necessary corrections to the previous work entitled {\\it A polynomial Time Algorithm to Solve The Max-atom Problem} (arXiv:2106.08854v1). The max-atom-problem (MAP) deals with system of scalar inequalities (called atoms or max-atom) of the form: $x \\leq a + \\max(y,z)$. Where $a$ is a real number and $x,y$ and $z$ belong to the set of the variables of the whole MAP. A max-atom is said to be positive if its scalar $a$ is $\\geq 0$ and stricly negative if its scalar $a <0$. A MAP will be said to be positive if all atoms are positive. In the case of non positive MAP we present a saturation principle for system of vectorial inequalities of the form $x \\leq A x + b$ in the so-called $(\\max,+)$-algebra assuming some properties on the matrix $A$. Then, we apply such principle to explore all non-trivial solutions (ie $\\neq -\\infty$). We deduce a strongly polynomial method to express all solutions of a non positive MAP. In the case a positive MAP which has always the vector $x^{1}=(0)$ as trivial solution we show that looking for all solutions requires the enumeration of all elementary circuits in a graph associated with the MAP. However, we propose a strongly polynomial method wich provides some non trivial solutions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-26T13:20:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q15",
      "68Q25"
    ],
    "keywords": [
      "max atom problem",
      "non positive map",
      "polynomial time algorithm",
      "strongly polynomial method wich",
      "non trivial solutions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "fr",
      "license": "arXiv",
      "status": "editable"
    }
  }
}