Interval matrices with Monge property

DOI10.21136/AM.2020.0370-19MaRDI QIDQ6331805arXivFDO

Authors Martin Černý

Publication date 25 December 2019

Published in arXiv

Full work available at URL https://doi.org/10.21136/AM.2020.0370-19

Mathematics Subject Classification ID

Error analysis and interval analysis (65G99) Linear programming (90C05)

arXiv classification

math.CO

Abstract: We generalize Monge property of real matrices for interval matrices. We define two classes of interval matrices with Monge property - in a strong and in a weak sense. We study fundamental properties of both classes. We show several different characterizations of the strong Monge property. For weak Monge property we give a polynomial characterization and several sufficient and necessary conditions. For both classes we study closure properties. We further propose a generalization of an algorithm by Deineko & Filonenko which for a given matrix returns row and column permutations such that the permuted matrix is Monge if the permutations exist.

This page was built for publication: Interval matrices with Monge property

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