Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2106.08854 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916370132762624 |
|---|---|
| author | Lahlou, Chams Truffet, Laurent |
| author_facet | Lahlou, Chams Truffet, Laurent |
| contents | In this paper we consider $m$ ($m \geq 1$)conjunctions of Max-atoms that is atoms of the form $\max(z,y) + r \geq x$, where the offset $r$ is a real constant and $x,y,z$ are variables. We show that the Max-atom problem (MAP) belongs to $\textsf{P}$. Indeed, we provide an algorithm which solves the MAP in $O(n^{6} m^{2} + n^{4} m^{3} + n^{2} m^{4})$ operations, where $n$ is the number of variables which compose the max-atoms. As a by-product other problems also known to be in $\textsf{NP} \cap \textsf{co-NP}$ are in $\textsf{P}$. P1: the problem to know if a tropical cone is trivial or not. P2: problem of tropical rank of a tropical matrix. P3: parity game problem. P4: scheduling problem with AND/OR precedence constraints. P5: problem on hypergraph (shortest path). P6: problem in model checking and $μ$-calculus. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_08854 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A polynomial Time Algorithm to Solve The Max-atom Problem Lahlou, Chams Truffet, Laurent Combinatorics 68Q15, 68Q25 In this paper we consider $m$ ($m \geq 1$)conjunctions of Max-atoms that is atoms of the form $\max(z,y) + r \geq x$, where the offset $r$ is a real constant and $x,y,z$ are variables. We show that the Max-atom problem (MAP) belongs to $\textsf{P}$. Indeed, we provide an algorithm which solves the MAP in $O(n^{6} m^{2} + n^{4} m^{3} + n^{2} m^{4})$ operations, where $n$ is the number of variables which compose the max-atoms. As a by-product other problems also known to be in $\textsf{NP} \cap \textsf{co-NP}$ are in $\textsf{P}$. P1: the problem to know if a tropical cone is trivial or not. P2: problem of tropical rank of a tropical matrix. P3: parity game problem. P4: scheduling problem with AND/OR precedence constraints. P5: problem on hypergraph (shortest path). P6: problem in model checking and $μ$-calculus. |
| title | A polynomial Time Algorithm to Solve The Max-atom Problem |
| topic | Combinatorics 68Q15, 68Q25 |
| url | https://arxiv.org/abs/2106.08854 |