Complete Solution of Tropical Vector Inequalities Using Matrix Sparsification

M. Akian, S. Gaubert, A. Guterman: Tropical polyhedra are equivalent to mean payoff games. Int. J. Algebra Comput. 22 (2012), Article ID 1250001, 43 pages. citation_journal_title=J. Comb. Theory, Ser. A; citation_title=The number of extreme points of tropical polyhedra; citation_author=X Allamigeon, S Gaubert, R D Katz; citation_volume=118; citation_publication_date=2011; citation_pages=162-189; citation_doi=10.1016/j.jcta.2010.04.003; citation_id=CR2 citation_title=Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley Series in Probability and Statistics; citation_publication_date=1992; citation_id=CR3; citation_author=F L Baccelli; citation_author=G Cohen; citation_author=G J Olsder; citation_author=J-P Quadrat; citation_publisher=Wiley citation_title=Max-Linear Systems: Theory and Algorithms; citation_publication_date=2010; citation_id=CR4; citation_author=P Butkovič; citation_publisher=Springer citation_journal_title=Ekon.-Mat. Obz.; citation_title=An elimination method for finding all solutions of the system of linear equations over an extremal algebra; citation_author=P Butkovič, G Hegedüs; citation_volume=20; citation_publication_date=1984; citation_pages=203-215; citation_id=CR5 citation_journal_title=Discrete Appl. Math.; citation_title=A strongly polynomial algorithm for solving two-sided linear systems in max-algebra; citation_author=P Butkovič, K Zimmermann; citation_volume=154; citation_publication_date=2006; citation_pages=437-446; citation_doi=10.1016/j.dam.2005.09.008; citation_id=CR6 citation_journal_title=J. Inst. Math. Appl.; citation_title=An algebra for network routing problems; citation_author=B A Carré; citation_volume=7; citation_publication_date=1971; citation_pages=273-294; citation_doi=10.1093/imamat/7.3.273; citation_id=CR7 citation_title=The Algebraic Theory of Semigroups. Vol. 1; citation_publication_date=1961; citation_id=CR8; citation_author=A H Clifford; citation_author=G B Preston; citation_publisher=American Mathematical Society citation_journal_title=Math. Program.; citation_title=Projections in minimax algebra; citation_author=R A Cuninghame-Green; citation_volume=10; citation_publication_date=1976; citation_pages=111-123; citation_doi=10.1007/BF01580656; citation_id=CR9 citation_title=Minimax Algebra; citation_publication_date=1979; citation_id=CR10; citation_author=R A Cuninghame-Green; citation_publisher=Springer citation_title=Minimax algebra and applications; citation_publication_date=1994; citation_id=CR11; citation_author=R A Cuninghame-Green; citation_publisher=Academic Press citation_journal_title=Theor. Comput. Sci.; citation_title=The equation A⊗x = B⊗y over (max,+); citation_author=R A Cuninghame-Green, P Butkovič; citation_volume=293; citation_publication_date=2003; citation_pages=3-12; citation_doi=10.1016/S0304-3975(02)00228-1; citation_id=CR12 citation_journal_title=Linear Algebra Appl.; citation_title=Bases in max-algebra; citation_author=R A Cuninghame-Green, P Butkovič; citation_volume=389; citation_publication_date=2004; citation_pages=107-120; citation_doi=10.1016/j.laa.2004.03.022; citation_id=CR13 citation_journal_title=Linear Algebra Appl.; citation_title=Max-algebra and pairwise comparison matrices. II; citation_author=L Eisner, P van den Driessche; citation_volume=432; citation_publication_date=2010; citation_pages=927-935; citation_doi=10.1016/j.laa.2009.10.005; citation_id=CR14 citation_journal_title=Linear Algebra Appl.; citation_title=The tropical analogue of polar cones; citation_author=S Gaubert, R D Katz; citation_volume=431; citation_publication_date=2009; citation_pages=608-625; citation_doi=10.1016/j.laa.2009.03.012; citation_id=CR15 citation_journal_title=J. Symb. Comput.; citation_title=Tropical linear-fractional programming and parametric mean payoff games; citation_author=S Gaubert, R D Katz, S Sergeev; citation_volume=47; citation_publication_date=2012; citation_pages=1447-1478; citation_doi=10.1016/j.jsc.2011.12.049; citation_id=CR16 citation_title=Semirings and Affine Equations Over Them: Theory and Applications; citation_publication_date=2003; citation_id=CR17; citation_author=J S Golan; citation_publisher=Kluwer Academic citation_title=Graphs, Dioids and Semirings: New Models and Algorithms; citation_publication_date=2008; citation_id=CR18; citation_author=M Gondran; citation_author=M Minoux; citation_publisher=Springer citation_title=Max Plus at Work. Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications; citation_inbook_title=Princeton Series in Applied Mathematics; citation_publication_date=2006; citation_id=CR19; citation_author=B Heidergott; citation_author=G J Olsder; citation_author=J van der Woude; citation_publisher=Princeton University Press citation_journal_title=Discrete Appl. Math.; citation_title=On two-sided max-linear equations; citation_author=D Jones; citation_volume=254; citation_publication_date=2019; citation_pages=146-160; citation_doi=10.1016/j.dam.2018.06.011; citation_id=CR20 citation_title=Idempotent Analysis and Its Applications; citation_publication_date=1997; citation_id=CR21; citation_author=V N Kolokoltsov; citation_author=V P Maslov; citation_publisher=Kluwer Academic citation_journal_title=Vestn. St. Petersbg. Univ., Math.; citation_title=Solution of generalized linear vector equations in idempotent algebra; citation_author=N K Krivulin; citation_volume=39; citation_publication_date=2006; citation_pages=16-26; citation_id=CR22 citation_journal_title=Optimization; citation_title=A multidimensional tropical optimization problem with a non-linear objective function and linear constraints; citation_author=N Krivulin; citation_volume=64; citation_publication_date=2015; citation_pages=1107-1129; citation_doi=10.1080/02331934.2013.840624; citation_id=CR23 citation_journal_title=Linear Algebra Appl.; citation_title=Extremal properties of tropical eigenvalues and solutions to tropical optimization problems; citation_author=N Krivulin; citation_volume=468; citation_publication_date=2015; citation_pages=211-232; citation_doi=10.1016/j.laa.2014.06.044; citation_id=CR24 citation_journal_title=J. Log. Algebr. Methods Program.; citation_title=Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling; citation_author=N Krivulin; citation_volume=89; citation_publication_date=2017; citation_pages=150-170; citation_doi=10.1016/j.jlamp.2017.03.004; citation_id=CR25 citation_journal_title=J. Log. Algebr. Methods Program.; citation_title=Complete algebraic solution of multidimensional optimization problems in tropical semifield; citation_author=N Krivulin; citation_volume=99; citation_publication_date=2018; citation_pages=26-40; citation_doi=10.1016/j.jlamp.2018.05.002; citation_id=CR26 citation_journal_title=Linear Algebra Appl.; citation_title=An algorithm to describe the solution set of any tropical linear system A ⊗ x = B ⊗ x; citation_author=E Lorenzo, M J de la Puente; citation_volume=435; citation_publication_date=2011; citation_pages=884-901; citation_doi=10.1016/j.laa.2011.02.014; citation_id=CR27 citation_title=Multiorder, Kleene stars and cyclic projectors in the geometry of max cones; citation_inbook_title=Tropical and Idempotent Mathematics; citation_publication_date=2009; citation_pages=317-342; citation_id=CR28; citation_author=S Sergeev; citation_publisher=American Mathematical Society citation_journal_title=Linear Algebra Appl.; citation_title=Basic solutions of systems with two max-linear inequalities; citation_author=S Sergeev, E Wagneur; citation_volume=435; citation_publication_date=2011; citation_pages=1758-1768; citation_doi=10.1016/j.laa.2011.02.033; citation_id=CR29 citation_title=Tropical cones defined by max-linear inequalities; citation_publication_date=2009; citation_id=CR30; citation_author=E Wagneur; citation_author=L Truffet; citation_author=F Faye; citation_author=M Thiam; citation_publisher=American Mathematical Society citation_journal_title=Am. Math. Mon.; citation_title=A note on a generalization of Boolean matrix theory; citation_author=M Yoeli; citation_volume=68; citation_publication_date=1961; citation_pages=552-557; citation_doi=10.1080/00029890.1961.11989717; citation_id=CR31 citation_journal_title=Ekon.-Mat. Obz.; citation_title=A general separation theorem in extremal algebras; citation_author=K Zimmermann; citation_volume=13; citation_publication_date=1977; citation_pages=179-201; citation_id=CR32