M. Akian, S. Gaubert, and M. Sharify, Tropical approximation of matrix eigenvalues

S. Gaubert, L. Grigori, and M. Sharify, A parallel optimal assignment algorithm based on diagonal scaling, SIAM workshop on combinatorial scientific computing (CSC09), pp.67-79, 2009.

S. Gaubert, L. Grigori, and M. Sharify, A parallel preprocessing for the optimal assignment problem based on diagonal scaling, 6th international workshop on parallel matrix algorithms and applications (PMAA10), pp.67-79, 2010.

S. Gaubert and M. Sharify, Tropical scaling of polynomial eigenvalue problem Poster representation, Congrès SMAI, 2009.

S. Gaubert and M. Sharify, Tropical scaling of polynomial eigenvalue problems, 1st Montreal workshop on idempotent and tropical mathematics, p.33, 2009.

S. Gaubert and M. Sharify, Tropical scaling of polynomial eigenvalue problems, SIAM conference on applied linear algebra (LA09), 2009.

S. Gaubert and M. Sharify, Tropical Scaling of Polynomial Matrices, Proceedings of the third Multidisciplinary International Symposium on Positive Systems: Theory and Applications
DOI : 10.1007/978-3-642-02894-6_28

L. Of, Eprint doi:10, pp.291-303, 2009.

M. Sharify, S. Gaubert, and L. Grigori, A parallel preprocessing for the optimal assignment problem based on diagonal scaling. submitted. Also: arXiv, pp.67-79, 2011.

S. Sk, R. Ahmad, and . Alam, Pseudospectra, critical points and multiple eigenvalues of matrix polynomials, Linear Algebra and its Applications, vol.430, issue.4, pp.1171-1195, 2009.

M. Akian, R. Bapat, and S. Gaubert, Perturbation of eigenvalues of matrix pencils and the optimal assignment problem, Comptes Rendus Mathematique, vol.339, issue.2, pp.103-108, 2004.
DOI : 10.1016/j.crma.2004.05.001

R. [. Akian, S. Bapat, and . Gaubert, Min-plus methods in eigenvalue perturbation theory and generalised Lidskii-Vishik-Ljusternik theorem. arXiv:math.SP/0402090, pp.34-48, 2005.

R. [. Akian, S. Bapat, and . Gaubert, Max-plus algebras, Handbook of Linear Algebra (Discrete Mathematics and Its Applications, pp.10-14, 2006.

I. [. Amestoy, D. Duff, B. Ruiz, and . Uçar, A Parallel Matrix Scaling Algorithm, High Performance Computing for Computational Science - VECPAR 2008, pp.301-313, 2008.
DOI : 10.1007/978-3-540-92859-1_27
URL : https://hal.archives-ouvertes.fr/hal-00803489

S. [. Akian, A. Gaubert, and . Guterman, Linear independence over tropical semirings and beyond, Proceedings of the International Conference on Tropical and Idempotent Mathematics, pp.1-38, 2009.
DOI : 10.1090/conm/495/09689
URL : http://arxiv.org/abs/0812.3496

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 Journal on Control and Optimization, vol.47, issue.2, pp.817-848, 2008.
DOI : 10.1137/060655286
URL : https://hal.archives-ouvertes.fr/inria-00071395

. [. Amir-moez, Khayyam's Solution of Cubic Equations, Mathematics Magazine, vol.35, issue.5, pp.269-271, 1962.
DOI : 10.2307/2688197

P. [. Burkard and . Butkovi?, Finding all essential terms of a characteristic maxpolynomial, Discrete Applied Mathematics, vol.130, issue.3, pp.367-380, 2003.
DOI : 10.1016/S0166-218X(03)00223-3

R. [. Butkovi?, S. Cuninghame-green, and . Gaubert, Reducible Spectral Theory with Applications to the Robustness of Matrices in Max-Algebra, SIAM Journal on Matrix Analysis and Applications, vol.31, issue.3, pp.1412-1431, 2009.
DOI : 10.1137/080731232

[. Baccelli, G. Cohen, G. J. Olsder, and J. Quadrat, Synchronization and linearity. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics An algebra for discrete event systems, pp.10-14, 1992.

[. Burkard, M. Dell-'amico, S. Martello, R. Bhatia, L. Elsner et al., Assignment problems Bounds for the variation of the roots of a polynomial and the eigenvalues of a matrix, Society for Industrial and Applied Mathematics (SIAM) Linear Algebra Appl, vol.70, issue.142, pp.195-209, 1990.

Y. Brenier, U. Frisch, M. Henon, G. Loeper, S. Matarrese et al., Reconstruction of the early Universe as a convex optimization problem, Monthly Notices of the Royal Astronomical Society, vol.346, issue.2, pp.501-524, 2003.
DOI : 10.1046/j.1365-2966.2003.07106.x
URL : https://hal.archives-ouvertes.fr/hal-00012457

G. Birkhoff, Three observations on linear algebra, Univ. Nac. Tucumán . Revista A, vol.5, pp.147-151, 1946.

T. Bewley and E. Kohlberg, The Asymptotic Theory of Stochastic Games, Mathematics of Operations Research, vol.1, issue.3, pp.197-208, 1976.
DOI : 10.1287/moor.1.3.197

W. Peter, M. Buchen, and . Kelly, The maximum entropy distribution of an asset inferred from option prices, Journal of Financial and Quantitative Analysis, issue.01, pp.31143-159, 1996.

A. [. Borwein, R. D. Lewis, and . Nussbaum, Entropy Minimization, DAD Problems, and Doubly Stochastic Kernels, Journal of Functional Analysis, vol.123, issue.2, pp.264-307, 1994.
DOI : 10.1006/jfan.1994.1089
URL : http://doi.org/10.1006/jfan.1994.1089

P. Butkovic and L. Murfitt, Calculating essential terms of a characteristic maxpolynomial. CEJOR Cent, Eur. J. Oper. Res, vol.8, issue.3, pp.237-246, 2000.

J. [. Belongie, J. Malik, and . Puzicha, Shape matching and object recognition using shape contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.24, issue.4, pp.509-522, 2002.
DOI : 10.1109/34.993558

[. Basu, R. Pollack, and M. Roy, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics, vol.10, p.75, 2006.
DOI : 10.1007/978-3-662-05355-3
URL : https://hal.archives-ouvertes.fr/hal-01083587

T. [. Bapat and . Raghavan, Nonnegative matrices and applications, of Encyclopedia of Mathematics and its Applications, p.84, 1997.
DOI : 10.1017/CBO9780511529979

A. Richard and . Brualdi, The DAD theorem for arbitrary row sums, Proc. Amer. Math. Soc, vol.45, pp.189-194, 1974.

]. R. Bsvdd95, D. P. Bapat, P. Stanford, and . Van-den-driessche, Pattern properties and spectral inequalities in max algebra, SIAM J. Matrix Anal. Appl, vol.16, issue.3, pp.964-976, 1995.

P. [. Bu? and . Tvrdík, Towards auction algorithms for large dense assignment problems, Computational Optimization and Applications, vol.74, issue.1, pp.411-436, 2009.
DOI : 10.1007/s10589-007-9146-5

[. Butkovi?, Max-linear Systems: Theory and Algorithms, 2010.
DOI : 10.1007/978-1-84996-299-5

. [. Cuninghame-green, Process synchronization in a steelworks-a problem of feasibility, Proceedings of the Second International Conference on Operational Research, pp.323-328, 1960.

. [. Cuninghame-green, The characteristic maxpolynomial of a matrix, Journal of Mathematical Analysis and Applications, vol.95, issue.1
DOI : 10.1016/0022-247X(83)90139-7

. [. Cuninghame-green, Minimax algebra and applications, of Advances in Imaging and Electron Physics, pp.1-121, 1994.

P. [. Cuninghame-green and . Meijer, An algebra for piecewise-linear minimax problems, Discrete Applied Mathematics, vol.2, issue.4, pp.267-294, 1980.
DOI : 10.1016/0166-218X(80)90025-6

S. [. Cohen, J. P. Gaubert, and . Quadrat, Hahn-Banach separation theorem for max-plus semimodules, Optimal Control and Partial Differential Equations, pp.325-334, 2001.

J. Cirasella, D. S. Johnson, L. A. Mcgeoch, and W. Zhang, The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests, Lecture Notes in Computer Science, vol.2153, pp.32-59, 2001.
DOI : 10.1007/3-540-44808-X_3

P. [. Cohen, J. P. Moller, M. Quadrat, and . Viot, Linear system theory for discrete event systems, The 23rd IEEE Conference on Decision and Control, pp.539-544, 1984.
DOI : 10.1109/CDC.1984.272058

[. Cohen and S. Gaubert-jean-pierre-quadrat, Max-plus algebra and system theory: Where we are and where to go now, Annu. Rev. Control, issue.1, pp.207-219, 1999.

+. Ctcg, J. Cochet-terrasson, G. Cohen, S. Gaubert, M. M. Gettrick et al., Numerical computation of spectral elements in max-plus algebra, p.14, 1998.

Y. Cheng, V. Wu, R. T. Collins, A. R. Hanson, and E. M. Riseman, <title>Maximum-weight bipartite matching technique and its application in image feature matching</title>, Visual Communications and Image Processing '96, p.3, 1996.
DOI : 10.1117/12.233261

A. Dasdan and R. K. Gupta, Faster maximum and minimum mean cycle algorithms for system-performance analysis, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.17, issue.10, pp.889-899, 1997.
DOI : 10.1109/43.728912

M. [. Dinic and . Kronrod, An algorithm for solving the assignment problem, Dokl. Akad. Nauk SSSR, vol.189, pp.23-25, 1969.

J. [. Duff and . Koster, On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix, SIAM Journal on Matrix Analysis and Applications, vol.22, issue.4, pp.973-996, 2000.
DOI : 10.1137/S0895479899358443

[. Edmonds and R. M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf, pp.93-96, 1969.
DOI : 10.1007/3-540-36478-1_4

S. Erlander, Entropy in linear programs, Math. Programming, pp.137-151, 1981.
DOI : 10.1007/BF01584236

J. Franklin and J. Lorenz, On the scaling of multidimensional matrices, Linear Algebra and its Applications, vol.114, issue.115, pp.717-735, 1989.
DOI : 10.1016/0024-3795(89)90490-4

W. Hung-yuan-fan, P. Lin, and . Van-dooren, Normwise scaling of second order polynomial matrices, SIAM J. Matrix Anal. Appl, vol.26, issue.34, pp.252-256, 2004.

M. [. Forsberg, A. Passare, and . Tsikh, Laurent Determinants and Arrangements of Hyperplane Amoebas, Advances in Mathematics, vol.151, issue.1, pp.45-70, 2000.
DOI : 10.1006/aima.1999.1856

[. Fang, J. R. Rajasekera, and H. J. Tsao, Entropy optimization and mathematical programming. International Series in Operations Research & Management Science, p.72, 1997.
DOI : 10.1007/978-1-4615-6131-6

L. Michael, R. E. Fredman, and . Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach, vol.34, issue.3, pp.596-615, 1987.

S. Gaubert, Two lectures on max-plus algebra, Proceedings of the 26th Spring School on Theoretical Computer Science and Automatic Control, p.15, 1998.

S. Gaubert, Max-plus and tropical convexity unified: Some unexpected results. Seminar on Applications of Tropical Algebra, 2009.

C. [. Galántai, Perturbation bounds for polynomials, Numerische Mathematik, vol.67, issue.4, pp.77-100, 2008.
DOI : 10.1007/s00211-007-0124-8

E. Gassner and B. Klinz, A fast parametric assignment algorithm with applications in max-algebra. Networks, pp.61-77, 2010.

M. [. Gondran and . Minoux, Linear Algebra in Dioids: A Survey of Recent Results, North-Holland Math. Stud, vol.95, issue.2, pp.147-163, 1984.
DOI : 10.1016/S0304-0208(08)72960-8

V. Andrew and . Goldberg, An efficient implementation of a scaling minimumcost flow algorithm, J. Algorithms, vol.22, issue.1, pp.1-29, 1997.

]. R. Gra72 and . Graham, An efficient algorithm for determining the convex hull of a finite planar set, Inf. Proc. Lett, vol.1, issue.4, pp.132-133, 1972.

[. Huang, Y. Chen, Y. Lin, and Y. Hsu, Data path allocation based on bipartite weighted matching, Conference proceedings on 27th ACM/IEEE design automation conference , DAC '90, pp.499-504, 1990.
DOI : 10.1145/123186.123350

J. Nicholas, R. Higham, F. Li, and . Tisseur, Backward error of polynomial eigenproblems solved by linearization, SIAM J. Matrix Anal. Appl, vol.29, issue.4, pp.1218-1241, 2007.

J. Nicholas, D. S. Higham, F. Mackey, and . Tisseur, The conditioning of linearizations of matrix polynomials, SIAM J. Matrix Anal. Appl, vol.28, issue.4, pp.1005-1028, 2006.

]. L. Hol93 and . Holm, Protein Structure Comparison by Alignment of Distance Matrices, Journal of Molecular Biology, vol.233, issue.70, pp.123-138, 1993.

J. Nicholas, F. Higham, and . Tisseur, Bounds for eigenvalues of matrix polynomials Special issue on accurate solution of eigenvalue problems, Linear Algebra Appl, vol.358, pp.5-22, 2003.

G. [. Itenberg, E. Mikhalkin, and . Shustin, Tropical algebraic geometry. Oberwolfach seminars. Birkhäuser, p.11, 2007.
DOI : 10.1007/978-3-0346-0048-4
URL : https://hal.archives-ouvertes.fr/hal-00143239

]. E. Jay57 and . Jaynes, Information theory and statistical mechanics, II. Phys. Rev, vol.108, issue.2, pp.171-190, 1957.

G. J. Olsder and J. Van-der-woude, Max Plus at Work -Modeling and Analysis of Synchronized Systems, Princeton Series in Applied Mathematics, 2006.

R. M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos, pp.85-103, 1972.
DOI : 10.1007/978-3-540-68279-0_8

R. M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Mathematics, vol.23, issue.1, pp.309-311, 1978.
DOI : 10.1016/0012-365X(78)90078-X

C. Tjalling, M. Koopmans, and . Beckmann, Assignment problems and the location of economic activities, Econometrica, vol.25, pp.53-76, 1957.

]. B. Kir09, . Kh, and . Kirshtein, Complex roots of systems of tropical equations and stability of electrical power networks, Tropical and idempotent mathematics, pp.213-238, 2009.

[. Kiyohiro and M. Kazuo, Critical initial imperfection of structures, International Journal of Solids and Structures, vol.26, issue.8, pp.865-886, 1990.
DOI : 10.1016/0020-7683(90)90074-6

]. J. Kk92a, H. K. Kapur, and . Kesavan, Entropy optimization principles with applications, p.71, 1992.

]. L. Kk92b, B. Khachiyan, and . Kalantari, Diagonal matrix scaling and linear programming, SIAM J. Optim, vol.2, issue.4, pp.668-672, 1992.

V. [. Kolokoltsov and . Maslov, Idempotent analysis and its applications , volume 401 of Mathematics and its Applications, pp.1-10, 1997.

A. Philip and . Knight, The Sinkhorn-Knopp algorithm: convergence and applications, SIAM J. Matrix Anal. Appl, vol.30, issue.1, pp.261-275, 2008.

D. [. Knight and . Ruiz, A fast algorithm for matrix balancing, Web Information Retrieval and Linear Algebra Algorithms, number 07071 in Dagstuhl Seminar Proceedings Internationales Begegnungs-und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, pp.82-89, 2007.
DOI : 10.1093/imanum/drs019

]. H. Kuh55 and . Kuhn, The Hungarian method for the assignment problem, Naval Res. Logist. Quart, vol.2, pp.83-97, 1955.

[. Lin, H. Chang, and Y. Lin, A study on tools and algorithms for 3-d protein structures alignment and comparison, International Computer Symposium, p.3, 2004.

J. [. Li, SuperLU DIST: A Scalable Distributedmemory Sparse Direct Solver for Unsymmetric linear systems, ACM Transactions on Mathematical Software, vol.29, issue.2, pp.3-71, 2003.

V. [. Litvinov, G. B. Maslov, and . Shpiz, Idempotent functional analysis: an algebraic approach, Mathematical Notes, vol.69, issue.5/6, pp.696-729, 2001.
DOI : 10.1023/A:1010266012029

J. [. Lee and . Orlin, On Very Large Scale Assignment Problems, Large scale optimization, pp.206-244, 1993.
DOI : 10.1007/978-1-4613-3632-7_12

A. [. Linial, A. Samorodnitsky, and . Wigderson, A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents, Combinatorica, vol.20, issue.4, pp.545-568, 2000.
DOI : 10.1007/s004930070007

T. Markwig, A field of generalised puiseux series for tropical geometry. to appear in Rend, Semin. Mat. Torino, p.76, 2009.

[. Marden, Geometry of polynomials Mathematical Surveys, 1966.

M. William and . Mceneaney, Max-plus methods for nonlinear control and estimation . Systems & Control: Foundations & Applications, Birkhäuser Boston Inc, issue.1, 2006.

G. Mikhalkin, Enumerative tropical algebraic geometry in R 2, J. Amer

]. L. Mir60 and . Mirsky, Symmetric gauge functions and unitarily invariant norms, Quart. J. Math. Oxford Ser, vol.11, issue.2, pp.50-59, 1960.

[. Mackey, N. Mackey, C. Mehl, and V. Mehrmann, Vector Spaces of Linearizations for Matrix Polynomials, SIAM Journal on Matrix Analysis and Applications, vol.28, issue.4, pp.971-1004, 2006.
DOI : 10.1137/050628350

H. [. Menon and . Schneider, The spectrum of a nonlinear operator associated with a matrix, Linear Algebra and its Applications, vol.2, issue.3, pp.321-334, 1969.
DOI : 10.1016/0024-3795(69)90034-2

G. [. Moler and . Stewart, An Algorithm for Generalized Matrix Eigenvalue Problems, SIAM Journal on Numerical Analysis, vol.10, issue.2, pp.241-256, 1973.
DOI : 10.1137/0710024

S. [. Maslov, Samborski? ?, editors. Idempotent analysis, Advances in Soviet Mathematics. Amer. Math. Soc, vol.13, issue.1, 1992.

K. Murota, Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation, SIAM Journal on Computing, vol.19, issue.6, pp.1132-1161, 1990.
DOI : 10.1137/0219077

J. [. Malajovich and . Zubelli, Tangent Graeffe iteration, Numerische Mathematik, vol.89, issue.4, pp.749-782, 2001.
DOI : 10.1007/s002110100278
URL : http://arxiv.org/abs/math/9908150

A. [. Nesterov and . Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), vol.13, p.77, 1994.
DOI : 10.1137/1.9781611970791

M. Olschowka and A. Neumaier, A new pivoting strategy for Gaussian elimination, Linear Algebra and its Applications, vol.240, pp.131-151, 1996.
DOI : 10.1016/0024-3795(94)00192-8

A. Ostrowski, Recherches sur la m??thode de graeffe et les z??ros des polynomes et des s??ries de laurent, Acta Mathematica, vol.72, issue.0, pp.99-155, 1940.
DOI : 10.1007/BF02546329

A. Ostrowski, Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent, Chapitres III et IV. Acta Math, vol.72, issue.2, pp.157-257, 1940.

Y. Victor and . Pan, Solving a polynomial equation: Some history and recent progress, SIAM Rev, vol.39, pp.187-220, 1997.

]. G. Par02 and . Parisi, Euclidean random matrices, the glass transition and the boson peak, The European Physical Journal E: Soft Matter and Biological Physics, vol.9, issue.3, pp.213-218, 2002.

[. Pin, Tropical semirings, pp.50-69, 1998.
DOI : 10.1017/CBO9780511662508.004
URL : https://hal.archives-ouvertes.fr/hal-00113779

M. Passare and A. Tsikh, Amoebas: their spines and their contours, Idempotent mathematics and mathematical physics, pp.275-288, 2005.
DOI : 10.1090/conm/377/06997

[. Richter-gebert, B. Sturmfels, and T. Theobald, First steps in tropical geometry, Contemp. Math. Amer. Math. Soc, vol.377, issue.2, pp.289-317, 2005.
DOI : 10.1090/conm/377/06998

R. [. Rockafellar and . Wets, Variational analysis. Number v. 317 in Grundlehren der mathematischen Wissenschaften, p.56, 1998.

H. Michael and . Schneider, Matrix scaling, entropy minimization, and conjugate duality. I. Existence conditions, Linear Algebra Appl, vol.114115, pp.785-813, 1989.

[. Sahni and T. Gonzalez, P-Complete Approximation Problems, Journal of the ACM, vol.23, issue.3
DOI : 10.1145/321958.321975

I. Simon, Limited subsets of a free monoid, 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), pp.143-150, 1978.
DOI : 10.1109/SFCS.1978.21

R. Sinkhorn and P. Knopp, Concerning nonnegative matrices and doubly stochastic matrices, Pacific Journal of Mathematics, vol.21, issue.2, pp.343-348, 1967.
DOI : 10.2140/pjm.1967.21.343

]. W. Spe38 and . Specht, Zur theorie der algebraischen gleichungen, Jahr. DMV, vol.48, issue.2, pp.142-145, 1938.

C. E. Shannon and W. Weaver, The Mathematical Theory of Communication, p.72, 1949.

H. Michael, S. A. Schneider, and . Zenios, A comparative study of algorithms for matrix balancing, Oper. Res, vol.38, pp.439-455, 1990.

A. Tarski, A Decision Method for Elementary Algebra and Geometry, p.76, 1951.
DOI : 10.1007/978-3-7091-9459-1_3

[. Teran, F. M. Dopico, and D. S. Mackey, Fiedler companion linearizations and the recovery of minimal indices, Siam Journal on Matrix Analysis and Applications, pp.31-34, 2010.

F. Tisseur, Backward error and condition of polynomial eigenvalue problems, Proceedings of the International Workshop on Accurate Solution of Eigenvalue Problems, pp.339-361, 1998.
DOI : 10.1016/S0024-3795(99)00063-4

. [. Valiron, Sur les fonctionsentì eres d'ordre nul et d'ordre fini et en particulier les fonctionsàfonctionsà correspondancerégulì ere, Réimprimé dans les annales de la faculté des sciences de Toulous, p.20, 1914.

]. O. Vir01 and . Viro, Dequantization of real algebraic geometry on logarithmic paper, European Congress of Mathematics, pp.135-146, 2000.

]. N. Vor67 and . Vorobyev, Extremal algebra of positive matrices, Elektron. Informationsverarbeitung und Kybernetik, vol.3, issue.2, pp.39-71, 1967.

]. K. Zim77 and . Zimmermann, A general separation theorem in extremal algebras, Ekonom.-Mat. Obzor, vol.13, issue.2 2, pp.179-201, 1977.