Geodesic
Tropical semimodules of dimension two
Algebra i analiz, Tome 26 (2014) no. 2, pp. 216-228.

Voir la notice de l'article provenant de la source Math-Net.Ru

The tropical arithmetic operations on $\mathbb R$ are defined as $a\oplus b=\min\{a,b\}$ and $a\otimes b=a+b$. In the paper, the concept of a semimodule is discussed, which is rather ill-behaved in tropical mathematics. The semimodules $S\subset\mathbb R^n$ having topological dimension two are studied and it is shown that any such $S$ has a finite weak dimension not exceeding $n$. For a fixed $k$, a polynomial time algorithm is constructed that decides whether $S$ is contained in some tropical semimodule of weak dimension $k$ or not. This result provides a solution of a problem that has been open for eight years.
Keywords: tropical mathematics, linear algebra, computational complexity. 
@article{AA_2014_26_2_a5,
     author = {Ya. Shitov},
     title = {Tropical semimodules of dimension two},
     journal = {Algebra i analiz},
     pages = {216--228},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/AA_2014_26_2_a5/}
}
TY  - JOUR
AU  - Ya. Shitov
TI  - Tropical semimodules of dimension two
JO  - Algebra i analiz
PY  - 2014
SP  - 216
EP  - 228
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AA_2014_26_2_a5/
LA  - en
ID  - AA_2014_26_2_a5
ER  - 
%0 Journal Article
%A Ya. Shitov
%T Tropical semimodules of dimension two
%J Algebra i analiz
%D 2014
%P 216-228
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AA_2014_26_2_a5/
%G en
%F AA_2014_26_2_a5
Ya. Shitov. Tropical semimodules of dimension two. Algebra i analiz, Tome 26 (2014) no. 2, pp. 216-228. http://geodesic.mathdoc.fr/item/AA_2014_26_2_a5/

[1] Akian M., Gaubert S., Guterman A., “Linear independence over tropical semirings and beyond”, Contemp. Math., 495, Amer. Math. Soc., Providence, RI, 2009, 1–38 | DOI | MR | Zbl

[2] Baccelli F., Cohen G., Olsder G. J., Quadrat J. P., Synchronization and linearity. An algebra for discrete event systems, John Wiley Sons, Ltd., Chichester, 1992 | MR

[3] Barvinok A. I., “Two algorithmic results for the traveling salesman problem”, Math. Oper. Res., 21:1 (1996), 65–84 | DOI | MR | Zbl

[4] Develin M., “The moduli space of $n$ tropically collinear points in $\mathbb R^d$”, Collect. Math., 56:1 (2005), 1–19 | MR | Zbl

[5] Develin M., Sturmfels B., “Tropical convexity”, Doc. Math., 9 (2004), 1–27, (electronic) | MR | Zbl

[6] Develin M., Santos F., Sturmfels B., “On the rank of a tropical matrix”, Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ., 52, Cambridge Univ. Press, Cambridge, 2005, 213–242 | MR | Zbl

[7] Einsiedler M., Kapranov M., Lind D., “Non-Archimedean amoebas and tropical varieties”, J. Reine Angew. Math., 601 (2006), 139–157 | MR | Zbl

[8] Ferrante J., Rackoff C., “A decision procedure for the first order theory of real addition with order”, SIAM J. Comput., 4 (1975), 69–76 | DOI | MR | Zbl

[9] Gaubert S., “Methods and applications of $(\max,+)$ linear algebra”, STACS 97 (Lübek, 1997), Lecture Notes in Comput. Sci., 1200, Springer, Berlin, 1997, 261–282 | DOI | MR

[10] Golan J. S., Semirings and their applications, Kluwer Acad. Publ., Dordrecht, 1999 | MR

[11] Litvinov G., Maslov V., “The correspondence principle for idempotent calculus and some computer applications”, Publ. Newton Inst., 11, Cambridge Univ. Press, Cambridge, 1998, 420–443 | MR

[12] Shitov Ya., “The complexity of tropical matrix factorization”, Adv. in Math., 254 (2014), 138–156 | DOI | MR | Zbl

[13] Viro O., “Dequantization of real algebraic geometry on logarithmic paper”, European Congress of Math., v. 1, Progr. Math., 201, Birkhäuser, Basel, 2001, 135–146 | MR | Zbl

[14] Wagneur E., “Moduloids and pseudomodules. 1. Dimension theory”, Discrete Math., 98:1 (1991), 57–73 | DOI | MR | Zbl