Papers on max-plus or tropical algebra, tropical convexity, dynamic programming, discrete event dynamic systems, non-linear Perron-Frobenius theory, linear algebra,...

1 Papers on max-plus or tropical algebra, tropical convexity, dynamic programming, discrete event dynamic systems, non-linear Perron-Frobenius theory, linear algebra,...

Papers on max-plus or tropical algebra, tropical convexity, dynamic programming, discrete event dynamic systems, non-linear Perron-Frobenius theory...

This page contains abstracts and eprints. To obtain reprints of the papers lacking here, send an email to Stephane.Gaubert@inria.fr

Journal, conference articles, ...

Several introductive texts of (max,+) algebra and Discrete event systems
Publication list in pdf (with some active links)
Publications available on arxiv
Papers are sorted by inverse chronological order
Xavier Allamigeon and Pascal Capetillo and Stephane Gaubert, Stationary regimes of piecewise linear dynamical systems with priorities, 2024, arXiv:2411.12437
Marianne Akian, Stéphane Gaubert, Loïc Marchesini The Competive Spectral Radius of Families of Nonexpansive Mappings, 2024, arXiv:2410.21097
Piermarco Cannarsa, Stephane Gaubert, Cristian Mendico, Marc Quincampoix Analysis of the vanishing discount limit for optimal control problems in continuous and discrete time, Mathematical Control and Related Fields, 2024 doi:10.3934/mcrf.2024010 arXiv:2306.07234.
Marianne Akian, Xavier Allamigeon, Stéphane Gaubert, Sergei Sergeev Signed tropicalization of polars and application to matrix cones, arXiv:2305.05637.
Marianne Akian, Stephane Gaubert, and Louis Rowen. Semiring systems arising from hyperrings, Journal of Pure and Applied Algebra, 228(6):107584, June 2024. doi:10.1016/j.jpaa.2023.107584,
Stéphane Gaubert, Yiannis Vlassopoulos Directed Metric Structures arising in Large Language Models, 2024, arXiv:2410.21097
Marianne Akian, Stéphane Gaubert, Ulysse Naepels, Basile Terver Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration, Proceedings of MFCS 2023, doi:10.4230/LIPICS.MFCS.2023.10, arXiv:2305.02458.
Marianne Akian and Antoine Béreau and Stéphane Gaubert, The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems, Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, 2023, doi:10.1145/3597066.3597089, hal-04117544v3
Marianne Akian, Stephane Gaubert, Hanieh Tavakolipour Factorization of polynomials over the symmetrized tropical semiring and Descartes' rule of sign over ordered valued fields, 2023, arXiv:2301.05483
Marianne Akian, Stéphane Gaubert, Shanqing Liu A Multi-Level Fast-Marching Method For The Minimum Time Problem, SIAM J. Control and Opt, 62(6), pp2963--2991, 2024, doi:10.1137/23M1563657, arXiv:2303.10705.
Quentin Jacquet, Wim van Ackooij, Clémence Alasseur, Stéphane Gaubert A Quantization Procedure for Nonlinear Pricing with an Application to Electricity Markets, Proceedings of IEEE CDC 2023, arXiv:2303.17394.
Shmuel Friedland, Stéphane Gaubert Bit-complexity estimates in geometric programming, and application to the polynomial-time computation of the spectral radius of nonnegative tensors, arXiv:2301.10637.
Quentin Jacquet, Wim van Ackooij, Clémence Alasseur, Stéphane Gaubert, Ergodic control of a heterogeneous population and application to electricity pricing, Proc. of CDC 2022, arXiv:2204.01410.
Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz, Mateusz Skomra: Universal Complexity Bounds Based on Value Iteration for Stochastic Mean Payoff Games and Entropy Games, Information and Computation, 302, 2025, doi:10.1016/j.ic.2024.105236, arXiv:2206.09044 This is an extended version of an article originally published in the Proceedings of ICALP 2022: 110:1-110:20, originally entitled ``Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games'', LIPIcs-ICALP-2022-110_.pdf.
Thierry Garaix, Stéphane Gaubert, Julie Josse, Nicolas Vayatis and Amandine Véber, Decision-making tools for healthcare structures in times of pandemic (Editorial), Anaesth. Crit. Care Pain Med. 41 (2022), 101052.
Pierre-Cyril Aubin-Frankowski and Stéphane Gaubert, Tropical reproducing kernels and optimization, Integral Eq. and Operator Theory, 2024, doi:10.1007/s00020-024-02769-4, arXiv:2202.11410.
Xavier Allamigeon, Marin Boyet and Stéphane Gaubert, Computing Transience Bounds of Emergency Call Centers: a Hierarchical Timed Petri Net Approach, arXiv:2202.02752, in Proc. of PETRI NETS 2022, number 13288 in Springer LNCS.
Xavier Allamigeon, Stéphane Gaubert and Nicolas Vandame, No self-concordant barrier interior point method is strongly polynomial, arXiv:2201.02186, 2022, in Proceedings of STOC 2022: 54th Annual ACM Symposium on Theory of Computing.
Maxime Grangereau, Wim van Ackooij, and St{\'{e}}phane Gaubert. Multi-stage stochastic alternating current optimal power flow with storage: Bounding the relaxation gap. Electric Power Systems Research, 206:107774, May 2022. doi:10.1016/j.epsr.2022.107774>/A>
Marianne Akian, Stéphane Gaubert, and Sara Vannucci, Ambitropical geometry, hyperconvexity and zero-sum games, arXiv:2108.07748, 2021, revised version 2023.
Quentin Jacquet, Wim van Ackooij, Clémence Alasseur, Stéphane Gaubert, Quadratic regularization of bilevel pricing problems and application to electricity retail markets. Eur. J. Oper. Res., Vol 313(3), pp. 841--657, 2023, doi:10.1016/j.ejor.2023.05.006 , arXiv:2110.02765
Marianne Akian, Stéphane Gaubert, Yang Qi and Omar Saadi, Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria, SIAM J. Disc. Math, 37(2), 2023 arXiv:2106.01930, doi:10.1137/21m1428297,
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig, What Tropical Geometry Tells Us about the Complexity of Linear Programming, SIAM Rev., 63(1), 123--164, 2021, SIGEST Award paper, doi:10.1137/20M1380211
Maël Forcier, Stephane Gaubert, Vincent Leclère, Exact quantization of multistage stochastic linear problems, to appear in SIAM J. Opt., arXiv:2107.09566, 2021.
Xavier Allamigeon, Stéphane Gaubert and Frédéric Meunier Tropical complementarity problems and Nash equilibria, SIAM Disc. Math., 37(3), 2023, arXiv:2012.05314, 2020
Xavier Allamigeon, Abdellah Aznag, Stéphane Gaubert, Yassine Hamdi The tropicalization of the entropic barrier, arXiv:2010.10205, 2020
Marianne Akian, Stéphane Gaubert, Zheng Qu, Omar Saadi, Multiply Accelerated Value Iteration for Non-Symmetric Affine Fixed Point Problems and application to Markov Decision Processes, SIAM J. Matrix Analysis, 43(1), 2022, arXiv:2009.10427, 2020.
Stéephane Gaubert, Marianne Akian, Xavier Allamigeon, Marin Boyet, Baptiste Colin, Théotime Grohens, Laurent Massoulié, David P. Parsons, Frédéric Adnet, Erick Chanzy, Laurent Goix, Frédéric Lapostolle, Eric Lecarpentier, Christophe Leroy, Thomas Loeb, Jean-Sébastien Marx, Caroline Télion, Laurent Tréluyer and Pierre Carli, Understanding and monitoring the evolution of the Covid-19 epidemic from medical emergency calls: the example of the Paris area, Comptes Rendus -- Mathématique, Volume 358, issue 7 (2020), p. 843-875, doi:10.5802/crmath.99 also arXiv:2005.14186
COVID-19 APHP-Universities-INRIA-INSERM Group, collective name for Frédéric Adnet, Marin Boyet, Jean-Jacques Avrane, Frédéric Batteux, Pierre-Yves Boëlle, Jérémie Boutet, Vincent Calvez, Pierre Carli, Pascal Chansard, Charlotte Chollet, François Crémieux, Diane Descamps, Stéphane Gaubert, Laurent Goix, Pierre Hausfater, Martin Hirsch, Eric Lecarpentier, Thomas Loeb, Jean-Sébastien Marx, Catherine Paugam, Renaud Piarroux, Bruno Riou (corresponding author), Remi Salomon, Caroline Telion, and Antoine Vieillard-Baron. Early indicators of intensive care unit bed requirement during the COVID-19 epidemic: A retrospective study in Ile-de-France region, France, PLOS ONE, 2020, doi:10.1371/journal.pone.0241406.
M. Akian, L. Ganassali, S. Gaubert, L. Massoulié, Probabilistic and mean-field model of COVID-19 epidemics with user mobility and contact tracing, arXiv:2009.05304
Olivier Beaude, Pascal Benchimol, Stéphane Gaubert , Paulin Jacquot , and Nadia Oudjane, A Privacy-Preserving Method to Optimize Distributed Resource Allocation, SIAM J. Optim., 30(3), 2303--2336. doi:10.1137/19M127879X
Marianne Akian, Xavier Allamigeon, Marin Boyet, Stéphane Gaubert, A convex programming approach to solve posynomial systems, Proceedings of the International Congress on Mathematical Software 2020, TU Braunschweig, July 13-16, 2020, Bigatti, Anna Maria and Carette, Jacques and Davenport, James H. and Joswig, Michael and de Wolff, Timo, Eds, Lecture Notes in Computer Science, volume 12097, Springer, 2020 arXiv:2005.07124
Xavier Allamigeon, Marin Boyet, and Stéphane Gaubert, Piecewise Affine Dynamical Models of Timed Petri Nets -- Application to Emergency Call Centers, Proceedings of the Petri Nets conference, Paris, 2020, The extended version appeared in Fundamentae Informaticae, 183(3-4): 169--201 (2021), doi:10.3233/FI-2021-2086 arXiv:2004.09483
Stéphane Gaubert and Adi Niv, Tropical planar networks, Linear Algebra and its Applications, Volume 595, 15 June 2020, Pages 123-144, doi:10.1016/j.laa.2020.02.019 arXiv:1910.12934
Marianne Akian, Stéphane Gaubert, Zheng Qu, and Omar Saadi. Solving ergodic Markov decision processes and perfect information zero-sum stochastic games by variance reduced deflated value iteration. In Proc. of the 58th IEEE Conference on Decision and Control, 2019. arXiv:1909.06185
Paulin Jacquot, Olivier Beaude, Pascal Benchimol, Stéphane Gaubert, and Nadia Oudjane. A privacy-preserving disaggregation algorithm for non-intrusive management of flexible energy. In Proc. of the 58th IEEE Conference on Decision and Control, 2019. arXiv:1903.03053
M. Akian, S. Gaubert, A. Hochart A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors, Discrete & Continuous Dynnamical Systems - A, 40 :207, 2020, doi:10.3934/dcds.2020009 arXiv:1812.09871
Giuseppe C. Calafiore, Stephane Gaubert and Corrado Possieri. A universal approximation result for difference of log-sum-exp neural networks, IEEE Trans Neural Networks Learn Syst. 2020 Dec;31(12):5603--5612. doi:10.1109/TNNLS.2020.2975051 arXiv:1905.08503
R. Bhatia, S. Gaubert, T. Jain Matrix versions of the Hellinger distance, Letters in Mathematical Physics, 2019, published on line, doi:10.1007/s11005-019-01156-0 arXiv:1901.01378
G. C. Calafiore, S. Gaubert, and C. Possieri. Log-sum-exp neural networks and posynomial models for convex and log-log-convex data. IEEE Transactions on Neural Networks and Learning Systems, pages 1--12, 2019. doi:10.1109/TNNLS.2019.2910417 arXiv:1806.07850
S. Gaubert, N. Stott A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices, arXiv:1805.03284 Mathematical Control and Related Fields, September 2020, 10(3): 573-590. doi:10.3934/mcrf.2020011 An abridged version of this manuscript has been published in the Proceedings of 23rd International Symposium on Mathematical Theory of Networks and Systems (MTNS2018), Hong-Kong.
S. Friedland, S. Gaubert Spectral inequalities for nonnegative tensors and their tropical analogues, Vietnam Journal of Mathematics, Springer, 2020, Special Issue in the Honor of Volker Mehrmann, 48 (4), pp.893--928, arXiv:1804.00204
X. Allamigeon, S. Gaubert, R. Katz, M. Skomra Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming, arXiv:1802.07712, An abridged version of this manuscript has been published in the Proc. of 23rd International Symposium on Mathematical Theory of Networks and Systems Hong Kong University of Science and Technology, Hong Kong, July 16-20, 2018
X. Allamigeon, S. Gaubert, M. Skomra The tropical analogue of the Helton-Nie conjecture is true, Journal of Symbolic Computation, 91, pp 129--148, 2019, doi:10.1016/j.jsc.2018.06.017 arXiv:1801.02089, The results of this article were presented at the conference MEGA 2017 (International conference on effective methods in algebraic geometry).
X. Allamigeon, P. Benchimol, S. Gaubert, M. Joswig, Log-barrier interior point methods are not strongly polynomial, SIAM J. Appl. Algebra Geometry, Vol. 2, No. 1, pp. 140-178, 2018, [pdf]. doi:10.1137/17M1142132 arXiv:1708.01544 This supersedes our initial arXiv posting (arXiv:1405.4161). An extended version of this paper as appeared in SIAM (Sigest paper), 2021, see reference above.
S. Gaubert and M. McCaig, Approximating the Volume of Tropical Polytopes is Difficult, International Journal of Algebra and Computation Vol. 29, No. 02, 2019, arXiv:1706.06467 10.1142/S0218196719500061
S. Gaubert and N. Stott, Tropical Kraus maps for optimal control of switched systems , Proceedings of the 57th IEEE Annual Conference on Decision and Control (CDC), Melbourne, 2017, arXiv:1706.04471
D. Castella and S. Gaubert, Algèbre de groupe en caractéristique 1 et distances invariantes sur un groupe fini, Mathematische Zeitschrift, 289(1-2), pages 695--709 (2018), hal-01674503 doi:10.1007/s00209-017-1971-3, [html]
X. Allamigeon, S. Gaubert, E. Goubault, S. Putot and N. Stott. A fast method to compute disjunctive quadratic invariants of numerical programs, ACM Transactions on Embedded Computing Systems (TECS), 16(5), 2017. Special Issue ESWEEK 2017, CASES 2017, CODES + ISSS 2017 and EMSOFT 2017, Seoul, South Korea. doi:10.1145/3126502
X. Allamigeon, S. Gaubert, and V. Boeuf. Stationary solutions of discrete and continuous Petri nets with priorities, arXiv:1612.07661 Performance evaluation, volume 113, pp. 1-12, 2017 doi:10.1016/j.peva.2017.04.007. An abridged version of this article has appeared in the Proceedings of Valuetools 2016 (10th EAI International Conference on Performance Evaluation Methodologies and Tools).
J. Depersin, S. Gaubert, and M. Joswig. A tropical isoperimetric inequality, Article 27, 12 pp, Séminaire Lotharingien de Combinatoire, 78B, 2017, Proceedings of FPSAC 2017 (29th Conference on Formal Power Series and Algebraic Combinatorics, London) arXiv:1611.04148
M. Akian and S. Gaubert and A. Niv, Tropical compound matrix identities, Linear Algebra and Appl., 551:162--206, 2018, doi:10.1016/j.laa.2018.04.006, arXiv:1702.00980
M. Akian and S. Gaubert and J. Grand-Clément and Jérémie Guillaud, The operator approach to entropy games, Theor. Comp. Sys., 63(5):1089-1130, July 2019. An abridged version of this article has been published in the Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Leibniz International Proceedings in Informatics (LIPIcs), volume 66, pages 6:1--6:14, 2017. arXiv:1904.05151
X. Allamigeon, S. Gaubert, and M. Skomra. Tropical spectrahedra, Discrete Comput. Geom., 63, 507--548 (2020) doi:10.1007/s00454-020-00176-1, arXiv:1610.06746
S. Gaubert and A. Niv. Tropical totally positive matrices, J. of Algebra, 2018, 515, pp.511-544. doi:10.1016/j.jalgebra.2018.07.005, arXiv:1606.00238
X. Allamigeon, S. Gaubert, and M. Skomra. Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, Journal of Symbolic Computation Volume 85, March-April 2018, Pages 25--54. doi:10.1016/j.jsc.2017.07.002, A preliminary version appeared in Proceedings of ISSAC 2016. arXiv:1603.06916
M. Akian, R. B. Bapat and S. Gaubert. Non-archimedean valuations of eigenvalues of matrix polynomials, Linear Algebra and its Applications, volume 498, pages 592--627, 2016 doi:10.1016/j.laa.2016.02.036, arXiv:1601.00438 [bib]
M. Akian, S. Gaubert, and A. Hochart. Hypergraph conditions for the solvability of the ergodic equation for zero-sum games. Proceedings of the 55th IEEE Annual Conference on Decision and Control (CDC), Osaka, 2015. arXiv:1510.05396 [bib]
X. Allamigeon, S. Gaubert, E. Goubault, S. Putot ad N. Stott. A scalable algebraic method to infer quadratic invariants of switched systems In 2015 International Conference on Embedded Software, EMSOFT 2015, Amsterdam, Netherlands, October 4-9, 2015, pages 75--84, 2015 (best paper award). doi:10.1109/EMSOFT.2015.7318262 [bib] An extended version of the present article has been published in ACM Transactions on Embedded Computing Systems (TECS), Volume 15 Issue 4, August 2016, doi:10.1145/2932187
X. Allamigeon, V. Bœuf, and S Gaubert. Performance evaluation of an emergency call center: Tropical polynomial systems applied to timed petri nets. In S.~Sankaranarayanan and E.~Vicario, editors, Formal Modeling and Analysis of Timed Systems (FORMATS 2015), volume 9268 of LNCS, pages 10--26. Springer, 2015. arXiv:1508.06162, doi:10.1007/978-3-319-22975-1_2 [bib]
M. Akian, S. Gaubert, A. Hochart, Minimax Representation of Nonexpansive Functions and Application to Zero-Sum Recursive Games, Journal of Convex Analysis, 2018, arXiv:1605.04518
M. Akian, S. Gaubert, A. Hochart, Generic uniqueness of the bias vector of finite stochastic games with perfect information, Journal of Mathematical Analysis and Applications, 457(2) :1038--1064, 2018, doi:10.1016/j.jmaa.2017.07.017 arXiv:1610.09651. Extended version of arXiv:1411.1211 (see below).
M. Akian, S. Gaubert, A. Hochart, Generic uniqueness of the bias vector of mean payoff zero-sum games, arXiv:1411.1211. Proceedings of IEEE 53rd Annual Conference on Decision and Control (CDC 2014), Los Angeles, pp. 1581--1587 [bib] See arXiv:1610.09651 above for an extended version of this work.
X. Allamigeon, P. Benchimol, and S. Gaubert. The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), number 8572 in Lecture Notes in Computer Science, pages 89–100. Springer, 2014. arXiv:1406.5433, [bib]
M. Akian, S. Gaubert, A. Hochart, Ergodicity conditions for zero-sum games, Discrete and Continuous Dynamical Systems, series A, 35(9) :3901--3931, 2015. arXiv:1405.4658 [bib] An abridged version of this paper has appeared in the conference article: Fixed Point Sets of Payment-Free Shapley Operators and Structural Properties of Mean Payoff Games, Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, July 7-11, 2014, Groningen, The Netherlands, pp. 1438--1441. [bib], [pdf].
X. Allamigeon, P. Benchimol, S. Gaubert, M. Joswig, Long and winding central paths, arXiv:1405.4161 This is now superseded by arXiv:1708.01544
V. Calvez, P. Gabriel, S. Gaubert, Non-linear eigenvalue problems arising from growth maximization of positive linear dynamical systems, arXiv:1404.1868, Proceedings of IEEE 53rd Annual Conference on Decision and Control (CDC 2014), Los Angeles, pp. 1600--1607 [bib]
S. Gaubert, Z. Qu, Checking the strict positivity of Kraus maps is NP-hard , Inf. Proc. Letters, vol 118, pages 35-43, 2017, doi:10.1016/j.ipl.2016.09.008 arXiv:1402.1429
S. Gaubert, Z. Qu, and S. Sridharan. Maximizing concave piecewise affine functions on the unitary group. Optimization Letters, 10:4, pp 655-665, 2016. doi:10.1007/s11590-015-0951-y [bib]
S. Gaubert, Z. Qu, S. Sridharan, Bundle-based pruning in the max-plus curse of dimensionality free method, arXiv:1402.1436. An abridged version of this paper has appeared in the Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, July 7-11, 2014. Groningen, The Netherlands, pp. 166-172, [bib], [pdf]. Some of the materials here, completed with proofs, have been published in the journal article immediately above.
M. Akian, S. Gaubert, Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial, arXiv:1310.4953
M. Akian, S. Gaubert, A. Marchesini, Tropical bounds for eigenvalues of matrices, Linear Algebra and its Applications, 446:281--303, 2014, doi:10.1016/j.laa.2013.12.021, arXiv:1309.7319, [bib]
M. Akian, S. Gaubert, A. Guterman, Tropical Cramer Determinants Revisited, In G.L. Litvinov and S.N. Sergeev, editors, Proceedings of the International Conference on Tropical and Idempotent Mathematics, volume 616 of Contemporary Mathematics, pages 1–45. American Mathematical Society, 2014. arXiv:1309.6298. [bib]
X. Allamigeon, P. Benchimol, S. Gaubert, M. Joswig, Combinatorial simplex algorithms can solve mean payoff games, 2013, arXiv:1309.5925, to appear in SIAM J. Opt., [bib]
X. Allamigeon, U. Fahrenberg, S. Gaubert, R. Katz and A. Legay, Tropical Fourier-Motzkin elimination, with an application to real-time verification, International Journal of Algebra and Computation, Vol. 14, No. 5, pp. 569--607, 2014, 10.1142/S0218196714500258. arXiv:1308.2122, [bib]
X. Allamigeon, P. Benchimol, S. Gaubert and M. Joswig, Tropicalizing the Simplex Algorithm, 2013, SIAM J. Disc. Math. arXiv:1308.0454
S. Gaubert and Z. Qu, Dobrushin ergodicity coefficient for Markov operators on cones, Integral Equations and Operators Theory, published on line, doi:10.1007/s00020-014-2193-2, [bib], arXiv:1307.4649v3. The initial version of this article, arXiv:1307.4649v3. with title Markov operators on cones and non-commutative consensus, has appeared in the Proceedings of the European Control Conference ECC 2013, Zurich, July 17-19, pp 2693--2700, 2013, [bib].
V. Magron, X. Allamigeon, S. Gaubert, and B. Werner, Certification of Real Inequalities -- Templates and Sums of Squares, Math. Prog. B, published on line, doi:10.1007/s10107-014-0834-5, arXiv:1403.5899, [bib]. This is an improved and extended version of the conference article immediately below.
X. Allamigeon, S. Gaubert, V. Magron and B. Werner, Certification of Bounds of Non-linear Functions: the Templates Method , in Proceedings of CICM 2013 (Conferences on Intelligent Computer Mathematics, ``Calculemus'', Track A), Bath, July 8-12, 2013 arXiv:1307.3231. An improved and extended version has appeared in the journal article immediately above.
X. Allamigeon, S. Gaubert, V. Magron and B. Werner, Certification of inequalities involving transcendental functions: combining SDP and max-plus approximation, in Proceedings of the European Control Conference ECC 2013, Zurich, July 17-19, pp 2044--2250, 2013. arXiv:1307.7002
M. Akian and S. Gaubert and M. Sharify, Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots, Linear Algebra and Appl., vol 528, pp. 394-435, 2017arXiv:1304.2967, doi:10.1016/j.laa.2016.11.004
S. Gaubert and Z. Qu, Dobrushin ergodicity coefficient for Markov operators on cones, and beyond, arXiv:1302.5226, 2013. An abridged version of some of these results, together with an application to consensus problems, has appeared in the Proceedings of ECC 2013, see the reference above (arXiv:1307.4649).
S. Gaubert and Th. Lepoutre, Discrete limit and monotonicity properties of the Floquet eigenvalue in an age structured cell division cycle model J. Math. Biol., 71(6) :1663--1703, December 2015, doi:10.1007/s00285-015-0874-3, arXiv:1301.2151.
J. Bolte, S. Gaubert and G. Vigeral, Definable stochastic games arXiv:1301.1967, Mathematics of Operations Research, published on line, 2014, doi:10.1287/moor.2014.0666, [bib]
M. Akian, J. Cochet-Terrasson, S. Detournay and S. Gaubert, Policy iteration algorithm for zero-sum multichain stochastic games with mean payoff and perfect information arXiv:1208.0446, 2012.
S. Gaubert and Zheng Qu, The contraction rate in Thompson's part metric of order-preserving flows on a cone - application to generalized Riccati equations, Journal of Differential Equations, 256(8):2902–2948, 2014. arXiv:1206.0448, doi:10.1016/j.jde.2014.01.024, [bib].
M. Akian, S. Gaubert, and R. Nussbaum, Uniqueness of the fixed point of nonexpansive semidifferentiable maps, Trans. of AMS, 368(2) :1271--1320, February 2016. arXiv:1201.1536
M. Akian and S. Gaubert and R. Nussbaum, A Collatz-Wielandt characterization of the spectral radius of order-preserving homogeneous maps on cones, arXiv:1112.5968, 2011.
F. Billy, J. Clairambault, O. Fercoq, S. Gaubert, T. Lepoutre T. Ouillon, and S. Saitoh, Synchronisation and control of proliferation in cycling cell population models with age structure, Mathematics and Computers in Simulation, vol 96, pp. 66--94, 2014, 10.1016/j.matcom.2012.03.005, hal-00662885, [bib]
S. Gaubert, W. McEneaney and Zheng Qu, Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms arXiv:1109.5241, 2011, Proceedings of the 50th Conference on Decision and Control and European Control Conference (CDC-ECC 2011), Orlando, FL, USA, pages 1054-1061, doi:10.1109/CDC.2011.6161386, [bib].
S. Gaubert and W. McEneaney. Min-max spaces and complexity reduction in min-max expansions. Appl. Math. Optim., 65(3):315--348, June 2012. doi:10.1007/s00245-011-9158-5, [bib].
F. Billy, J. Clairambault, O. Fercoq, S. Gaubert, T. Lepoutre and T. Ouillon, Proliferation in Cell Population Models with Age Structure, AIP Conf. Proc., Volume 1389, pp. 1212--1215, 2011, 10.1063/1.3637834, [bib].
M. Sharify, S. Gaubert, L. Grigori, A parallel preprocessing for the optimal assignment problem based on diagonal scaling, arXiv:1104.3830, 2011.
M. Akian, S. Gaubert, V. Nitica, and I. Singer, Best approximation in max-plus semimodules, Linear Algebra and Appl., Volume 435, Issue 12, Pages 3261-3296, 2011, doi:10.1016/j.laa.2011.06.009 arXiv:1012.5492, [bib]
S. Gaubert and G. Vigeral. A maximin characterization of the escape rate of nonexpansive mappings in metrically convex spaces, Mathematical Proceedings of the Cambridge Philosophical Society, volume 152, pages 341-363, 2012, doi:10.1017/S0305004111000673 arXiv:1012.4765, [bib].
O. Fercoq, M. Akian, M. Bouhtou, S. Gaubert, Ergodic Control and Polyhedral approaches to PageRank Optimization, IEEE-TAC, 58(1):134–148, 2013. arXiv:1011.2348, doi:10.1109/TAC.2012.2226103, [bib].
S. Friedland and S. Gaubert. Submodular spectral functions of principal submatrices of an Hermitian matrix, extensions and applications, Linear Algebra and Appl., volume 438, number 10, pp. 3872--3884, May 2013. doi:10.1016/j.laa.2011.11.021, arXiv:1007.3478, [bib].
S. Gaubert and S. Sergeev. The level set method for the two-sided max-plus eigenproblem, J. Disc. Event Dynamic Systems, volume 23, number 2, pp. 105-134, June 2013, doi:10.1007/s10626-012-0137-z, arXiv:1006.5702, [bib].
T. M. Gawlitza, H. Seidl, A. Adje, S. Gaubert and E. Goubault, Abstract interpretation meets convex optimization, Journal of symbolic computation, 47(12):1416-1446, December 2012, Special issue on invariant generation and advanced techniques for reasoning about loops, doi:10.1016/j.jsc.2011.12.048, [bib].
S. Gaubert, R. Katz and S. Sergeev. Tropical linear-fractional programming and parametric mean payoff games. Journal of symbolic computation, volume 27, number 12, pages 1447-1478, 2012, arXiv:1101.3431, doi:10.1016/j.jsc.2011.12.049, [bib]. Journal version of a communication to the Third international Workshop on Invariant Generation (WING'2010), associated with the International Joint Conference on Automated Reasoning (IJCAR 2010), Edinburgh July 21, 2010.
J. Clairambault, S. Gaubert and T. Lepoutre. Circadian rhythm and cell population growth, Mathematical and Computer Modelling, Volume 53, Issues 7-8, April 2011, Pages 1558-1567 doi:10.1016/j.mcm.2010.05.034, arXiv:1006.3459, [bib].
X. Allamigeon, S. Gaubert, and R. Katz. Tropical polar cones, hypergraph transversals, and mean payoff games, Linear algebra and its Applications, Volume 435, Issue 7, 1 October 2011, Pages 1549-1574, doi:10.1016/j.laa.2011.02.004 . arXiv:1004.2778, [bib].
V. Blondel and S. Gaubert and N. Portier, The set of realizations of a max-plus linear sequence is semi-polyhedral Journal of Computer and System Sciences, volume 77 (2011) 820-833 doi:10.1016/j.jcss.2010.08.010, arXiv:1010.3685v1, [bib].
G. Sagnol, S. Gaubert and M. Bouhtou, Optimal monitoring on large networks by Successive c-Optimal Designs. Proceedings of the 22nd international teletraffic congress (ITC22), Amsterdam, The Netherlands, September 2010, doi:10.1109/ITC.2010.5608717, [pdf], [bib].
G. Sagnol, M. Bouhtou and S. Gaubert, Successive c-Optimal Designs : A scalable technique to optimize the measurements on large networks. Extended abstract (2 pages). Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, New York, NY, USA, June 2010, pp. 347--348, ISBN:978-1-4503-0038-4, doi:10.1145/1811039.1811080, [pdf], [bib].
M. Akian, S. Gaubert, and B. Lemmens. Stability and convergence in discrete convex monotone dynamical systems , Journal of Fixed Point Theory and Applications, Volume 9, Number 2, 295-325, 2011, doi:10.1007/s11784-011-0052-1, arXiv:1003.5346, [bib].
S. Gaubert, R. Katz, and S. Sergeev. Tropical linear programming and parametric mean payoff games. In Third international Workshop on Invariant Generation (WING’2010), associated with the International Joint Conference on Automated Reasoning (IJCAR 2010), Edinburgh July 21. 2010. [pdf]. An extended version of the present work has appeared in Journal of symbolic computation, volume 27, number 12, pages 1447-1478, 2012, see the bibliographic input above (arXiv:1101.3431).
J. Edmonds, S. Gaubert, and V. Gurvich, Sperner oiks, Electronic Notes in Discrete Mathematics, 36:1273--1280, 2010. Proceedings of ISCO 2010 - International Symposium on Combinatorial Optimization, doi:10.1016/j.endm.2010.05.161 [bib].
J. Edmonds, S. Gaubert, and V. Gurvich. Scarf oiks. Electronic Notes in Discrete Mathematics, 36:1281--1288, 2010. Proceedings of ISCO 2010 - International Symposium on Combinatorial Optimization, doi:10.1016/j.endm.2010.05.162, [bib].
A. Adje, S. Gaubert, E. Goubault. Coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis, Logical methods in Computer Science, Volume 8, issue 1, paper 1, doi:0.2168/LMCS-8(1:01)2012, arXiv:1111.5223, [bib]. This is the augmented journal version of the article originally published in the Proceedings of the 19th European Symposium on Programming (ESOP 2010), Lecture Notes in Computer Science 6012, Springer, pp 23--42, 2010 doi:978-3-642-11957-6_3
M. Akian, S. Gaubert, and A. Guterman. The correspondence between tropical convexity and mean payoff games, Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS 2010), 5-9 July, 2010, Budapest, Hungary, pp. 1295--1302, ISBN 978-963-311-370-7, [bib]. This is a conference paper announcing the results of the paper immediately below (arXiv:0912.2462).
M. Akian, S. Gaubert, and A. Guterman. Tropical polyhedra are equivalent to mean payoff games , International of Algebra and Computation, 22(1):125001 (43 pages), 2012. arXiv:0912.2462, doi:10.1142/S0218196711006674, [bib].
S. Gaubert. Max-plus algebraic tools for discrete event systems, static analysis, and zero sum games (extended abstract associated to an invited talk). In J. Ouaknine and F. Vaandrager, editors, Formal Modeling and Analysis of Timed Systems: 7th International Conference, FORMATS 2009, volume 5813 of LNCS, pages 7--11, Springer, 2009, doi:10.1007/978-3-642-04368-0_2, [bib].
S. Gaubert and R. Katz, Minimal half-spaces and external representation of tropical polyhedra , Journal of Algebraic Combinatorics, volume 33, number 3, pages 325-348, 2011 10.1007/s10801-010-0246-4, arXiv:0908.1586, [bib].
X. Allamigeon, S. Gaubert and R. Katz, The number of extreme points of tropical polyhedra, J. Comb. Theory series A, Volume 118, Issue 1, January 2011, Pages 162-189, 10.1016/j.jcta.2010.04.003, arXiv:0906.3492, [bib].
X. Allamigeon, S. Gaubert and E. Goubault, The tropical double description method, arXiv:1001.4119, 2010, Proceedings of the Symposium on Theoretical Aspects of Computer Science, 2010, Nancy, France (STACS'2010), pp 47-58, in volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), arXiv:1001.4119, doi:10.4230/LIPIcs.STACS.2010.2443, [bib].
X. Allamigeon, S. Gaubert and E. Goubault, Computing the vertices of tropical polyhedra using directed hypergraphs. Discrete Comp. Geom., 49(2):247–279, 2013. arXiv:0904.3436v3, doi:10.1007/s00454-012-9469-6, [bib]. An announcement of the results of this paper appeared in STACS, reference immediately above this one (arXiv:1001.4119).
S. Friedland, S. Gaubert, L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra and its Applications, 438(2):738–749, 2013. arXiv:0905.1626, doi:10.1016/j.laa.2011.02.042, [bib]. This has been selected among ``10 Notable Papers from Linear Algebra & Its Applications (LAA) published over the last 50 years'', at the occasion of the golden anniversary of LAA.
S. Gaubert, M. Sharify, Tropical Scaling of Polynomial Matrices, Proceedings of POSTA 09 (Positive Systems: Theory and Applications), Valencia, Spain, volume 389 in the Springer LNCIS series, pp 291--303, 2009, doi:10.1007/978-3-642-02894-6_28, also arXiv:0905.0121, [bib].
M. Di Loreto, S. Gaubert, R. Katz and J-J. Loiseau, Duality between invariant spaces for max-plus linear discrete event systems, SIAM J. Control Optim. Volume 48, Issue 8, pp. 5606-5628 (2010), doi:10.1137/090747191, arXiv:0901.2915, [bib].
M. Akian, S. Gaubert and V. Kolokoltsov, The Optimal Assignment Problem for a Countable State Space, Proceedings of the International Conference on Tropical and Idempotent Mathematics, G.L. Litvinov and S.N. Sergeev Eds, volume 495 of Contemporary Mathematics, pp. 39--60, AMS, 2009. Also arXiv:0812.4866.
M. Akian, S. Gaubert and A. Guterman, Linear independence over tropical semirings and beyond, Proceedings of the International Conference on Tropical and Idempotent Mathematics, G.L. Litvinov and S.N. Sergeev Eds, volume 495 of Contemporary Mathematics, pp. 1--38, AMS, 2009. Also arXiv:0812.3496.
J. Clairambault, S. Gaubert, T. Lepoutre, Comparison of Perron and Floquet eigenvalues in age structured cell division cycle models, Math. Model. Nat. Phenom., Vol. 4 No. 3, pp 183-209, 2009, doi:10.1051/mmnp/20094308, eprint arXiv:0812.0803.
P. Butkovic, R. A. Cuninghame-Green, S. Gaubert, Reducible spectral theory with applications to the robustness of matrices in max-algebra, SIAM J. Matrix Anal. Appl., volume 31, number 3, pp. 1412--1431, 2009, doi:10.1137/080731232, [pdf].
M. Akian, B. David, S. Gaubert. Un théorème de représentation des solutions de viscosité d'une équation d'Hamilton-Jacobi-Bellman ergodique dégénérée sur le tore, C.R. Acad. Sci. Paris, Ser I 346 (2008) 1149-1154, doi:10.1016/j.crma.2008.09.020
A. Adje, S. Gaubert and E. Goubault. Computing the smallest fixed point of nonexpansive mappings arising in game theory and static analysis of programs, arXiv:0806.1160, The initial version appeared in the Proceedings of MTNS'08, Blacksburg, Virginia, July 2008; an improved version has been published in Journal of Mathematical Analysis and Applications Volume 410, Issue 1, 1 February 2014, Pages 227, doi:10.1016/j.jmaa.2013.07.076
W.M. McEneaney, A. Deshpande, and S. Gaubert. Curse-of-complexity attenuation in the curse-of-dimensionality-free method for HJB PDEs. In Proc. of the 2008 American Control Conference, pages 4684--4690, Seattle, Washington, USA, June 2008, doi:10.1109/ACC.2008.4587234
S. Gaubert and F. Meunier. Carathéodory, Helly and the others in the max-plus world , Discrete and Computational Geometry, volume 43, number 3, pp 648-662, 2010 doi:10.1007/s00454-009-9207-x, also arXiv:0804.1361.
S. Gaubert and R. Katz. The tropical analogue of polar cones, Linear Algebra and its Applications, Volume 431, pages 608-625, 2009, eprint arXiv:0805.3688, doi: 10.1016/j.laa.2009.03.012
M. Akian, S. Gaubert, and A. Lakhoua Convergence analysis of the max-plus finite element method for solving optimal control problems, Proceedings of the 47th IEEE Conference on Decision and Control (CDC'08), pp 927--934, Cancun, Mexico, doi:10.1109/CDC.2008.4739501
X. Allamigeon, S. Gaubert, and E. Goubault. Inferring Min and Max Invariants Using Max-plus Polyhedra, In Proceedings of the 15th International Static Analysis Symposium (SAS'08), 2008, Springer LNCS number 5079, pp 189-204, doi:10.1007/978-3-540-69166-2_13
M. Bouhtou, S. Gaubert and G. Sagnol, Optimization of Network Traffic Measurement : A Semidefinite Programming Approach, Proceedings of the International Conference on Engineering Optimization (EngOpt 2008), June 1-5 2008, Rio de Janeiro, paper number 0615.
M. Akian, S. Gaubert, and L. Ninove, Multiple equilibria of nonhomogeneous Markov chains and self-validating web rankings, arXiv:math/0712.0469 [math.PR], 2007.
S. Gaubert and S. Sergeev, Cyclic projectors and separation theorems in idempotent convex geometry , Journal of Mathematical Sciences (Springer, New-York), Vol. 155, No. 6, pp.815--829, doi:10.1007/s10958-008-9243-8 (Russian version published in Fundamentalnaya i prikladnaya matematika, vol. 13 (2007), no. 4, pp. 33-52, also arXiv:math/0706.3347 [math.MG]
J. Clairambault, S. Gaubert, and B. Perthame, An inequality for the Perron and Floquet eigenvalues of monotone differential systems and age structured equations, arXiv:0704.3820 [math.SP], 2007, Comptes Rendus Mathematique, Volume 345, Issue 10, 15 November 2007, Pages 549-554, doi:10.1016/j.crma.2007.10.001.
S. Gaubert and E. Goubault and A. Taly and S. Zennou, Static Analysis by Policy Iteration on Relational Domains, Proc. of the 16th European Symposium on Programming (ESOP'07), Braga (Portugal), 24 March - 1 April, 2007, Springer's LNCS volume 4421, pages 237--252, doi:10.1007/978-3-540-71316-6_17,
M. Akian, S. Gaubert, C. Walsh, How to find horizon-independent optimal strategies leading off to infinity: a max-plus approach, arXiv:math.OC/0609243. Proc. of the 45th IEEE Conference on Decision and Control (CDC 2006), 13-15 Dec. 2006, San Diego, Pages: 5024-5029, doi:10.1109/CDC.2006.377830
J. Cochet-Terrasson and S. Gaubert, A policy iteration algorithm for zero-sum stochastic games with mean payoff, C. R. Acad. Sci. Paris, Ser. I 343 (2006), pp. 377-382, doi:10.1016/j.crma.2006.07.011, preprint hal/inria-00144146.
V. Dhingra and S. Gaubert, How to solve large scale deterministic games with mean payoff by policy iteration, ACM International Conference Proceeding Series; Vol. 180, article No.12 in the Proceedings of the 1st international conference on Performance evaluation methodolgies and tools (VALUETOOLS), Pisa, Italy, October 2006, ISBN:1-59593-504-5, doi:10.1145/1190095.1190110
M. Akian and S. Gaubert and N. Ninove, The T-PageRank: A Model of Self-Validating Effects of Web Surfing, Proceedings of the Second Multidisciplinary International Symposium on Positive Systems: Theory and Applications (POSTA'06), Grenoble, France, August 30 - September 1 2006, Lecture Notes in Control and Information Sciences, volume 341, 2006, pp. 239--246, Springer. doi:10.1007/11757344_31.
S. Gaubert and R. Katz, Max-plus convex geometry, in the Proceedings of the 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications of Kleene Algebra (RelMiCS/AKA 2006), R. A. Schmidt (Ed), Lecture Notes in Comput. Sci., volume 4136, pp. 192-206, 2006, Springer. doi:10.1007/11828563_13.
S. Gaubert and R. Katz, The Minkowski Theorem for Max-plus Convex Sets, , arXiv:math.GM/0605078, Linear Algebra and Appl., volume 421, pp. 356-369, 2007, doi:10.1016/j.laa.2006.09.019
M. Akian, S. Gaubert, and A. Lakhoua The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis, SIAM J. Control, vol 47, number 2, pp 817--848, 2008, doi:10.1137/060655286
M.Akian, R. Bapat, S. Gaubert, Max-plus algebras, Chapter 25 in the Handbook of Linear Algebra, L. Hogben, R. Brualdi, A. Greenbaum, and R. Mathias (editors), Discrete Mathematics and Its Applications, Volume 39, Chapman and Hall, 2007, ISBN 1-58488-510-6, Second Edition, ISBN 9781466507289, November 2013.
G. Cohen, S. Gaubert, and J.P. Quadrat Projection and aggregation in maxplus algebra, Current Trends in Nonlinear Systems and Control, in Honor of Petar Kokotovic and Turi Nicosia, Menini, Laura; Zaccarian, Luca; Abdallah, Chaouki T. (Eds.), Birkhauser, January 2006, [pdf],.
M. Akian, S. Gaubert, V. Kolokoltsov. Solutions of max-plus linear equations and large deviations, Proceedings of the joint 44th IEEE Conference on Decision and Control and European Control Conference ECC 2005 (CDC-ECC'05), Sevilla, Spain, Dec. 2005, pages 7787 - 7792, doi:10.1109/CDC.2005.1583420 arXiv:math.OC/0509279.
M. Akian, S. Gaubert, A. Lakhoua. The max-plus finite element method for optimal control problems: further approximation results, Proceedings of the joint 44th IEEE Conference on Decision and Control and European Control Conference ECC 2005 (CDC-ECC'05), Sevilla, Spain, Dec. 2005, pages 4505 - 4510, doi:10.1109/CDC.2005.1582872 arXiv:math.OC/0509250.
S. Gaubert Nonlinear Perron-Frobenius theory and discrete event systems, Actes du colloque Modélisation de Systèmes Réactifs (MSR'05), JESA vol. 39, pp. 175--190, 2005 (this is a short survey corresponding to an invited conference).
A. Costan, S. Gaubert, E. Goubault, M. Martel, S. Putot, A policy iteration algorithm for computing fixed points in static analysis of programs, appears in the Proceedings of the 17th International Conference on Computer Aided Verification (CAV'05), Edinburgh, Scotland, UK, July 2005, LNCS 3576, pp. 462--475, Springer. doi:doi:10.1007/11513988_46.
G. Cohen, S. Gaubert, and J.P. Quadrat L'algèbre des sandwichs, Pour la Science, pp. 56--63, Février 2005.
G. Cohen, S. Gaubert, E. Mancinelli, J.P. Quadrat and E. Rofman, On traffic light control, Mathematicae Notae, Boletin del Instituto de Matematica "Beppo Levi", Ano XLIII (2005), pp. 51-62, Universidad Nacional de Rosario Editora, Rosario, Argentina. (Preliminary version available as INRIA Report 4276, Sep. 2001.)
M. Akian, S. Gaubert, C. Walsh. The max-plus Martin boundary, Documenta Mathematica, volume 14, pp 195-240, 2009, also arXiv:math.MG/0412408.
M. Akian, S. Gaubert, B. Lemmens and R. Nussbaum. Iteration of order preserving subhomogeneous maps on a cone, Mathematical Proceedings of the Cambridge Philosophical Society, volume 140, pages 157--176, 2006. doi:doi:10.1017/S0305004105008832. Also arXiv:math.DS/0410084.
M. Akian, S. Gaubert and C. Walsh. Discrete max-plus spectral theory ESI Preprint 1485, arXiv:math.SP/0405225. Appears in Idempotent Mathematics and Mathematical Physics, G.L. Litvinov and V.P. Maslov, Eds, vol. 377 of Contemporary Mathematics, pp. 53--77, AMS, 2005.
M. Akian, S. Gaubert and A. Lakhoua. A max-plus finite element method for solving finite horizon deterministic optimal control problems, INRIA RR-5163, arXiv:math.OC/0404184. Proceedings of the Sixteenth International Symposium on Mathematical Theory of Networks and Systems (MTNS2004), Louvain, Belgique, Jul. 2004 (proceedings on cdrom, no page numbers).
M. Akian, S. Gaubert and V. Kolokoltsov. Set coverings and invertibility of functional Galois connections ESI Preprint 1447, arXiv:math.FA/0403441. Appears in Idempotent Mathematics and Mathematical Physics, G.L. Litvinov and V.P. Maslov, Eds, vol. 377 of Contemporary Mathematics, pp. 19--51, AMS, 2005.
M. Akian, R. Bapat and S. Gaubert. Perturbation of eigenvalues of matrix pencils and optimal assignment problem C. R. Acad. Sci. Paris, Série I, volume 339 (2004), pages 103-108. doi:doi:10.1016/j.crma.2004.05.001 Also arXiv:math.SP/0402438.
M. Akian, R. Bapat and S. Gaubert. Min-plus methods in eigenvalue perturbation theory and generalised Lidskii-Vishik-Ljusternik theorem arXiv:math.SP/0402090, (preliminary version as INRIA RR-5104, Feb. 04).
S. Gaubert and R. Katz. Reachability problems for products of matrices in semirings. INRIA RR-4944, Sep. 03. International Journal of Algebra and Computation, Vol. 16, No. 3 (2006) 603-627, doi:doi:10.1142/S021819670600313X arXiv:math.OC/0310028
G. Cohen, S. Gaubert and J.P. Quadrat and I. Singer. Max-plus convex sets and functions. ESI preprint 1341, Jul. 2003. arXiv:math.FA/0308166. Appears in Idempotent Mathematics and Mathematical Physics, G.L. Litvinov and V.P. Maslov, Eds, vol. 377 of Contemporary Mathematics, pp. 105--129, AMS, 2005.
G. Cohen, S. Gaubert and J.P. Quadrat. Duality and Separation Theorems in Idempotent Semimodules. Linear Algebra and Appl., Volume 379, pages 395--422, 2004. doi:10.1016/j.laa.2003.08.010 Also arXiv:math.FA/0212294.
M. Akian, S. Gaubert and V. Kolokoltsov. Invertibility of Functional Galois Connections. C. R. Acad. Sci. Paris, Série I, Vol. 335 (2002), p. 883-888. doi:10.1016/S1631-073X(02)02594-3 [pdf], [ps], [ps.gz]
S. Gaubert and R. Katz. Rational semimodules over the max-plus semiring and geometric approach of discrete event systems. Kybernetika, volume 40 (2004), number 2, pages 153-180. Czech Digital Mathematics Library #35586 Also arXiv:math.OC/0208014.
M. Akian and S. Gaubert. Spectral theorem for convex monotone homogeneous maps, and ergodic control, INRIA-RR-4273, October 2001, arXiv:math.SP/0110108 Nonlinear Analysis, TMA., volume 52, number 2, pages 637--679, 2003. doi:10.1016/S0362-546X(02)00170-0
M. Akian and R.B. Bapat and S. Gaubert. Generic asymptotics of eigenvalues using (min,+) algebra, Proceedings of the Satellite Workshop on Max-Plus Algebras, IFAC SSSC'01, Praha, Aug. 2001. [pdf], [ps], [ps.gz]
S. Gaubert and J. Gunawardena. The Perron-Frobenius Theorem for Homogeneous, Monotone Functions, Transactions of AMS. Volume 356, Number 12, Pages 4931--4950, 2004. doi:10.1090/S0002-9947-04-03470-1 arXiv:math.FA/0105091.
M. Akian and S. Gaubert. A spectral theorem for convex monotone homogeneous maps, Proceedings of the Satellite Workshop on Max-Plus Algebras, IFAC SSSC'01, Praha, Aug. 2001. Elsevier. [ps], [ps.gz] This is a short announce of the result which has been detailed in arXiv:math.SP/0110108.
G. Cohen, S. Gaubert and J.P. Quadrat. Hahn-Banach Separation Theorem for Max-Plus Semimodules, in Optimal Control and Partial Differential Equations, J.L. Menaldi, E. Rofman and A. Sulem Eds, IOS Press 2001. [pdf], [ps], [ps.gz]
J. Cochet-Terrasson and S. Gaubert, Policy Iteration Algorithm for Shortest Path Problems, October 2000.
S. Gaubert and D. Hong Series expansions of Lyapunov exponents and Forgetful Monoids. February, 2000. INRIA RR-3971 [pdf], [ps.gz]
S. Gaubert and J. Gunawardena. Existence of Eigenvectors for Monotone Homogeneous Functions. August 1999. Hewlett-Packard Technical Report HPL-BRIMS-99-08, [pdf], [ps.gz]. An improved version of this report appeared in the TAMS paper referenced above, arXiv:math.FA/0105091.
V. D. Blondel, S. Gaubert, and J. N. Tsitsiklis, Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard, IEEE Transactions on Automatic Control, Vol. 45, No. 9, Sep. 2000, pp 1762--1765. [pdf] doi:10.1109/9.880644 [ps.gz]
P. Butkovic and S. Gaubert, Sign-non-singular matrices and matrices with unbalanced determinant in symmetrised semirings, Linear Algebra and Appl., 301, pp. 195-201, 1999. doi:10.1016/S0024-3795(99)00201-3
S. Gaubert and A. Giua, Petri net languages and infinite subsets of $\bold N\sp m$ J. Comput. System Sci. 59 (1999), no. 3, 373--391. doi:10.1006/jcss.1999.1634, [pdf] [ps], [ps.gz]
G. Cohen, S. Gaubert and J.P. Quadrat, Max-plus algebra and System Theory: where we are and where to go now. Annual Reviews in Control, vol. 23, pp 207--219, 1999. 10.1016/S1367-5788(99)90091-3, [pdf]
S. Gaubert, J. Mairesse, Asymptotic Analysis of Heaps of Pieces and application to Timed Petri Nets, PNPM'99, Saragoza, Spain, Sep. 1999. doi:10.1109/PNPM.1999.796562, [pdf]
Stéphane Gaubert, Jeremy Gunawardena, A Non-Linear Hierarchy for Discrete Event Dynamical Systems, Proceedings of WODES'98, Cagliari, Italia, pp. 249-254, Aug 1998. [pdf], [ps], [ps.gz]
M. Akian, R. Bapat, S. Gaubert, Asymptotics of the Perron Eigenvalue and Eigenvector Using Max-Algebra, C.R.A.S., t. 327, Serie I, pp 927--932, 1998. doi:10.1016/S0764-4442(99)80137-2 RR-3450.pdf, RR-3450.ps,RR-3450.ps.gz
Jean Cochet-Terrasson, Guy Cohen, Stephane Gaubert, Michael Mc Gettrick, Jean-Pierre Quadrat, Numerical computation of spectral elements in max-plus algebra, IFAC Conference on System Structure and Control, 1998, Pergamon press, [pdf], [ps], [ps.gz]
Albert Benveniste and Stéphane Gaubert and Claude Jard, Monotone rational series and max-plus algebraic models of real-time systems, Proc. of the Fourth Workshop on Discrete Event Systems (WODES98), IEE, Cagliari, Italy, 1998. [pdf]
A. Benveniste and C. Jard and S. Gaubert, Algebraic techniques for timed systems, Proceedings of CONCUR'98 number 1466 in LNCS, Springer, 1998 (Nice, France, Septembre 1998). doi:10.1007/BFb0055636 [pdf]
Jean Cochet-Terrasson, Stéphane Gaubert, Jeremy Gunawardena, A constructive fixed point theorem for min-max functions, June 1997. Dynamics and Stability of Systems, Vol. 14, No. 4, pp 407-433, 1999. doi:10.1080/026811199281967
Stéphane Gaubert, Jeremy Gunawardena, The Duality Theorem for min-max Functions, June 1997. C.R.A.S, t. 326, Série I, p. 43--48, 1998. doi:10.1016/S0764-4442(97)82710-3
S. Gaubert, J. Mairesse, Modeling and Analysis of Timed Petri Nets using Heaps of Pieces, IEEE Trans. Aut. Control, 44(4):683--697, 1999. doi:10.1109/9.754807 [pdf], [ps],[ps.gz] An abridged version appeared in the Proceedings of the ECC97. ECC version.ps ECC version.ps.gz
Task Resource Models and (max,+) Automata, S. Gaubert, J. Mairesse, 1995. Appears in Idempotency, J. Gunawardena Ed. Collection of the Isaac Newton Institute, Cambridge University Press, 1998. Abstract.html, [ps], [ps.gz], [pdf]
Algebraic System Analysis of Timed Petri Nets, G. Cohen, S. Gaubert and J. P. Quadrat, 1995. Appears in Idempotency, J. Gunawardena Ed. Collection of the Isaac Newton Institute, Cambridge University Press, 1998. Abstract.html, [ps], [ps.gz], [pdf]
G. Cohen, S. Gaubert, J.P. Quadrat, Timed Event Graphs with Multipliers and Homogeneous Min-Plus Systems, IEEE-TAC, Vol 43, N. 9, Sep 1998. doi:10.1109/9.718621 [pdf], [ps], [ps.gz]
S. Gaubert, Peter Butkovi\v{c}, R. Cuninghame-Green, Minimal (max,+) Realization of Convex Sequences. SIAM J. on Control and Opt., Vol. 36, No. 1, Jan 1998. doi:10.1137/S036301299528534X Abstract [pdf, copyright SIAM]
S. Gaubert and M. Plus, Methods and Applications of (max,+) Linear Algebra, Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science Lubeck, Germany February 27 - March 1, 1997 (STACS'97), pp 261-282, LNCS 1200, Springer, 1997, doi:10.1007/BFb0023465 A survey paper with emphasis on linear algebra.
Max-Plus working group (collective name), Max-Plus-Times Linear Systems In: V.D. Blondel, E.D. Sontag, M. Vidyasagar, J.C. Willems (Eds.), Open Problems in Mathematical Systems and Control Theory, Communications and Control Engineering series, Springer Verlag, London, 1999.
G. Cohen, S. Gaubert, J.P. Quadrat, Linear Projectors in the max-plus Algebra, Proceedings of the 5th IEEE Mediterranean Conference on Control and Systems (MED'97), Cyprus, Jul. 1997. [ps], [pdf], [ps.gz]
J.P. Quadrat and the Max-Plus Working group (collective name), Min-Plus Linearity and statistical mechanics, Markov Processes and Related Fields, Vol. 3, N. 4, pp 565--587 (1997). [pdf], [ps], [ps.gz]
S. Gaubert, On the Burnside Problem for semigroups of matrices in the (max,+) algebra. Semigroup Forum, Vol. 52 (1996), pp. 271--292. doi:10.1007/BF02574104 Abstract.html, [pdf] [ps] The SF published version had a minor LaTeX numbering problem independent of the author (see the Corrigendum on the SF site). The version provided here is mathematically identical, but without this issue.
S. Gaubert and A. Giua, Petri Net Languages With Infinite Sets of Final Markings. Feb. 1995. Proceedings of WODES' 96. Edinburgh, Scotland, UK, 19-21 August, 1996. Abstract
G. Cohen and S. Gaubert and J.P. Quadrat, Asymptotic Throughput of Continuous Timed Petri Nets Proceedings of the 34th Conference on Decision and Control, New Orleans, Dec, 1995. doi:10.1109/CDC.1995.480646 Abstract.html, [ps], [ps.gz], [pdf]
G. Cohen, S. Gaubert, J.P. Quadrat, Kernels, images and projections in dioids. Proceedings of the third international workshop on Discrete Event Systems (WODES'96), IEE, Edinburgh, Scotland, UK, August 19-21, 1996. Abstract [ps] (size 3MB !), [ps.gz] (1.4MB) [pdf](0.7MB)
S. Gaubert and A. Giua, Deterministic Weak-and-Marked Petri Net Languages are Regular, IEEE-TAC, 41(12), Dec. 1996. doi:10.1109/9.545718 Abstract, [pdf], [ps], [ps.gz]
S. Gaubert, Performance Evaluation of (max,+) Automata, IEEE Trans. on Automatic Control, 40(12), pp. 2014--2025, Dec. 1995. doi:10.1109/9.478227 Abstract.html, [pdf], [ps] An anouncement of these results appeared in the Proceedings of the ECC93, Groningen, July 1993.
S. Gaubert, Resource Optimization and (min,+) Spectral Theory. IEEE Trans. on Automatic Control, 40(11) Nov. 1995. doi:10.1109/9.471219 Abstract.html, [pdf], [ps]
S. Gaubert, Rational Series over Dioids and Discrete Event Systems, Proc. of the 11th Conf. on Anal. and Opt. of Systems: Discrete Event Systems, number 199 in Lect. Notes. in Control and Inf. Sci, Springer, 1994 (June 1994, Sophia Antipolis). doi:10.1007/BFb0033554 Abstract.html, [ps], [ps.gz], [pdf],
G. Cohen and S. Gaubert and J.P. Quadrat, From first to second-order theory of linear discrete event systems, 12th IFAC, Sydney, Jul., 1993. Abstract.html.
M. Plus, A linear system theory for systems subject to synchronization and saturation constraints. Proceedings of the first European Control Conference Grenoble, July 1991. Abstract, [pdf] [ps.gz].
Cohen, G.; Gaubert, S.; Nikoukhah, R.; Quadrat, J.P., Second order theory of min-linear systems and its application to discrete event systems. Proceedings of the 30th CDC, Brighton, Dec. 1991. Abstract. doi:10.1109/CDC.1991.261654 [pdf]
S. Gaubert and C. Klimann, Rational computation in dioid algebra and its application to performance evaluation of Discrete Event Systems, In Algebraic computing in control, G. Jacob and F. Lamnabhi-Lagarrigue Eds, Lecture Notes in Control and Inf. Sci. number 165, 1991, Springer. doi:10.1007/BFb0006942 [pdf]
M. Plus, Linear systems in (max,+)-algebra, Proceedings of the 29th Conference on Decision and Control, Honolulu, pages 151-156, volume 1, Dec. 1990. doi:10.1109/CDC.1990.203566 Abstract.html, [pdf], [ps], [ps.gz]
S. Gaubert, An algebraic method for optimizing resources in timed event graphs. Proceedings of the 9th International Conference on Analysis and Optimization of Systems, A.Bensoussan and J.L. Lions Eds, Lecture Notes in Control and Information Sciences number 144, Springer 1990. Abstract.html
M. Plus, L'algèbre (max,+) et sa symétrisation ou l'algèbre des équilibres. Comptes Rendus à l'Académie des Sciences, Section Automatique, volume 311, number 4, pp 443--448, 1990. [pdf] (scanned file from Gallica).
G. Cohen and S. Gaubert and R. Nikoukhah and J.P. Quadrat, Convex analysis and spectral analysis of timed event graphs, Proceedings of the 28th Conf. Decision and Control, Tampa, FL, Dec., 1989, [pdf] doi:10.1109/CDC.1989.70401

Other texts

PhD Thesis. Theory of Linear Systems over Dioids, Thèse de l'Ecole Nationale Supérieure des Mines de Paris, Juillet 1992. (in French)
- Abstract
- psfiles.perchaper.gz
- All_The_Thesis.pdf (~2MB)

Bibliography

A bibliography on the (max,+) semiring. Bibliography.bib (BibTeX file) Bibliography.html (outdated now).

Software

Howard's algorithm for max-plus matrices. A fast c program to compute the cycle time of possibly very large (full or sparse) max-plus matrices. This program can be used independently or from the Maxplus toolbox of scilab
I developed a MAPLE package called MAX for (max,+) algebra.

S. Gaubert Updated November, 2014