Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.14256 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914924141215744 |
|---|---|
| author | Truffet, Laurent |
| author_facet | Truffet, Laurent |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_14256 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Looking for all solutions of the Max Atom Problem (MAP) Truffet, Laurent Combinatorics 68Q15 68Q25 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. |
| title | Looking for all solutions of the Max Atom Problem (MAP) |
| topic | Combinatorics 68Q15 68Q25 |
| url | https://arxiv.org/abs/2408.14256 |