General information
Latest issue
Impact factor
Journal history

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Fundam. Prikl. Mat.:

Personal entry:
Save password
Forgotten password?

Fundam. Prikl. Mat., 2007, Volume 13, Issue 4, Pages 31–52 (Mi fpm1063)  

This article is cited in 16 scientific papers (total in 16 papers)

Cyclic projectors and separation theorems in idempotent convex geometry

S. Gauberta, S. N. Sergeevb

a French National Institute for Research in Computer Science and Automatic Control, INRIA Paris - Rocquencourt Research Centre
b M. V. Lomonosov Moscow State University

Abstract: Semimodules over idempotent semirings like the max-plus or tropical semiring have much in common with convex cones. This analogy is particularly apparent in the case of subsemimodules of the $n$-fold Cartesian product of the max-plus semiring: It is known that one can separate a vector from a closed subsemimodule that does not contain it. Here we establish a more general separation theorem, which applies to any finite collection of closed subsemimodules with a trivial intersection. The proof of this theorem involves specific nonlinear operators, called here cyclic projectors on idempotent semimodules. These are analogues of the cyclic nearest-point projections known in convex analysis. We obtain a theorem that characterizes the spectrum of cyclic projectors on idempotent semimodules in terms of a suitable extension of Hilbert's projective metric. We also deduce as a corollary of our main results the idempotent analogue of Helly's theorem.

Full text: PDF file (261 kB)
References: PDF file   HTML file

English version:
Journal of Mathematical Sciences (New York), 2008, 155:6, 815–829

Bibliographic databases:

UDC: 512.643+512.558

Citation: S. Gaubert, S. N. Sergeev, “Cyclic projectors and separation theorems in idempotent convex geometry”, Fundam. Prikl. Mat., 13:4 (2007), 31–52; J. Math. Sci., 155:6 (2008), 815–829

Citation in format AMSBIB
\by S.~Gaubert, S.~N.~Sergeev
\paper Cyclic projectors and separation theorems in idempotent convex geometry
\jour Fundam. Prikl. Mat.
\yr 2007
\vol 13
\issue 4
\pages 31--52
\jour J. Math. Sci.
\yr 2008
\vol 155
\issue 6
\pages 815--829

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Gaubert S., Katz R.D., “The tropical analogue of polar cones”, Linear Algebra Appl., 431:5-7 (2009), 608–625  crossref  mathscinet  zmath  isi  elib
    2. Akian M., Gaubert S., Guterman A., “Linear independence over tropical semirings and beyond”, Tropical and idempotent mathematics, Contemp. Math., 495, Amer. Math. Soc., Providence, RI, 2009, 1–38  crossref  mathscinet  zmath  adsnasa  isi
    3. Sergeev S., “Multiorder, Kleene stars and cyclic projectors in the geometry of max cones”, Tropical and Idempotent Mathematics, Contemp. Math., 495, Amer. Math. Soc., Providence, RI, 2009, 317–342  crossref  mathscinet  zmath  isi
    4. Gaubert S., “Max-plus algebraic tools for discrete event systems, static analysis, and zero-sum games”, Formal modeling and analysis of timed systems, Lecture Notes in Computer Science, 5813, Springer, Berlin, 2009, 7–11  crossref  zmath  isi
    5. Gaubert S., Meunier F., “Carathéodory, Helly and the others in the max-plus world”, Discrete Comput. Geom., 43:3 (2010), 648–662  crossref  mathscinet  zmath  isi  elib
    6. Singer I., “Elementary topical functions on $b$-complete semimodules over $b$-complete idempotent semifields”, Linear Algebra Appl., 433:11–12 (2010), 2139–2146  crossref  mathscinet  zmath  isi
    7. Nitica V., Sergeev S., “On hyperplanes and semispaces in max-min convex geometry”, Kybernetika (Prague), 46:3 (2010), 548–557  mathscinet  zmath  isi
    8. Gaubert S., Katz R.D., “Minimal half-spaces and external representation of tropical polyhedra”, J. Algebr. Comb., 33:3 (2011), 325–348  crossref  mathscinet  zmath  isi  elib
    9. Allamigeon X., Gaubert S., Katz R.D., “The number of extreme points of tropical polyhedra”, J. Combin. Theory Ser. A, 118:1 (2011), 162–189  crossref  mathscinet  zmath  isi  elib
    10. Akian M., Gaubert S., Niţică V., Singer I., “Best approximation in max-plus semimodules”, Linear Algebra Appl., 435:12 (2011), 3261–3296  crossref  mathscinet  zmath  isi  elib
    11. Nitica V., Sergeev S., “An interval version of separation by semispaces in max-min convexity”, Linear Algebra Appl., 435:7 (2011), 1637–1648  crossref  mathscinet  zmath  isi  elib
    12. Akian M., Gaubert S., Guterman A., “Tropical polyhedra are equivalent to mean payoff games”, Internat. J. Algebra Comput., 22:1 (2012), 1250001, 43 pp.  crossref  mathscinet  zmath  isi  elib
    13. Singer I., Nitica V., “Topical Functions on Semimodules and Generalizations”, Linear Alg. Appl., 437:10 (2012), 2471–2488  crossref  mathscinet  zmath  adsnasa  isi
    14. Allamigeon X., Gaubert S., Goubault E., “Computing the Vertices of Tropical Polyhedra Using Directed Hypergraphs”, Discret. Comput. Geom., 49:2 (2013), 247–279  crossref  mathscinet  zmath  isi  elib
    15. Durcheva M.I., “An Application of Different Dioids in Public Key Cryptography”, Applications of Mathematics in Engineering and Economics (AMEE'14), AIP Conference Proceedings, 1631, eds. Venkov G., Pasheva V., Amer Inst Physics, 2014, 336–343  crossref  isi
    16. Hassani S., Mohebi H., “Characterizations of Minimal Elements of Topical Functions on Semimodules With Applications”, Linear Alg. Appl., 520 (2017), 104–124  crossref  mathscinet  zmath  isi  scopus
  • Фундаментальная и прикладная математика
    Number of views:
    This page:337
    Full text:100

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021