On integer images of max-plus linear mappings

DOI10.1016/J.DAM.2018.01.001MaRDI QIDQ1706117zbMATH OpenOpenAlexFDO

Authors Peter Butkovič

Publication date 21 March 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1709.09022

zbMATH Keywords

computational complexityinteger imagemax-linear mapping

Mathematics Subject Classification ID

Max-plus and related algebras (15A80) Matrix equations and identities (15A24)

Abstract: Let us extend the pair of operations (max,+) over real numbers to matrices in the same way as in conventional linear algebra. We study integer images of max-plus linear mappings. The question whether Ax (in the max-plus algebra) is an integer vector for at least one x has been studied for some time but polynomial solution methods seem to exist only in special cases. In the terminology of combinatorial matrix theory this question reads: is it possible to add constants to the columns of a given matrix so that all row maxima are integer? This problem has been motivated by attempts to solve a class of job-scheduling problems. We present two polynomially solvable special cases aiming to move closer to a polynomial solution method in the general case.

Recommendations

• On some properties of the image set of a max-linear mapping
• On the integer max-linear programming problem
• On integer eigenvectors and subeigenvectors in the max-plus algebra
• Introduction to max-linear programming
• Exploring the complexity of the integer image problem in the \(\max\)-algebra

Cites work

• scientific article; zbMATH DE number 3906559 (Why is no real title available?)
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 1358710 (Why is no real title available?)
• scientific article; zbMATH DE number 5019906 (Why is no real title available?)
• A MAX-plus model of ribosome dynamics during mRNA translation
• A characterization of the minimum cycle mean in a digraph
• A condition for the strong regularity of matrices in the minimax algebra
• A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing
• Applications of max algebra to diagonal scaling of matrices
• Assignment Problems
• Exploring the complexity of the integer image problem in the \(\max\)-algebra
• Extremals of the supereigenvector cone in max algebra: a combinatorial description
• Finding a bounded mixed-integer solution to a system of dual network inequalities
• Handbook of linear algebra
• Introduction to max-linear programming
• Max-algebra: The linear algebra of combinatorics?
• Max-linear systems. Theory and algorithms.
• Max-plus methods for nonlinear control and estimation.
• Minimax algebra
• On integer eigenvectors and subeigenvectors in the max-plus algebra
• On the integer max-linear programming problem
• On tropical supereigenvectors
• On visualization scaling, subeigenvectors and Kleene stars in max algebra
• Reducible spectral theory with applications to the robustness of matrices in max-algebra
• Tropical Convex Hull Computations
• Tropical geometry and its applications
• Tropical linear-fractional programming and parametric mean payoff games
• Tropical mathematics

Cited in

(6)

• New Multilinear Maps Over the Integers
• A strongly polynomial method for solving integer max-linear optimization problems in a generic case
• On some properties of the image set of a max-linear mapping
• Exploring the complexity of the integer image problem in the \(\max\)-algebra
• On the integer max-linear programming problem
• Introduction to max-linear programming

This page was built for publication: On integer images of max-plus linear mappings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1706117)