zbMATH — the first resource for mathematics

Interval matrices with Monge property. (English) Zbl 07285949
Summary: We generalize the Monge property of real matrices for interval matrices. We define two classes of interval matrices with the Monge property – in a strong and a weak sense. We study the fundamental properties of both types. We show several different characterizations of the strong Monge property. For the weak Monge property, we give a polynomial description and several sufficient and necessary conditions. For both classes, we study closure properties. We further propose a generalization of an algorithm by Deineko and Filonenko which for a given matrix returns row and column permutations such that the permuted matrix is Monge if the permutations exist.
65G99 Error analysis and interval analysis
90C05 Linear programming
PDF BibTeX Cite
Full Text: DOI
[1] Alefeld, G.; Mayer, G., Interval analysis: Theory and applications, J. Comput. Appl. Math. 121 (2000), 421-464
[2] Burkard, R. E.; Klinz, B.; Rudolf, R., Perspectives of Monge properties in optimization, Discrete Appl. Math. 70 (1996), 95-161
[3] Cechlárová, K.; Szabó, P., On the Monge property of matrices, Discrete Math. 81 (1990), 123-128
[4] Deineko, V. G.; Filonenko, V. L., On the reconstruction of specially structured matrices, Aktualnyje problemy EVM i programmirovanije. Dnepropetrovsk, DGU (1979), Russian
[5] Garloff, J.; Adm, M.; Titi, J., A survey of classes of matrices possessing the interval property and related properties, Reliab. Comput. 22 (2016), 1-14
[6] Greenlaw, R.; Hoover, H. J.; Ruzzo, W. L., Limits to Parallel Computation: \(P\)-Completeness Theory, Oxford University Press, Oxford (1995)
[7] Hladík, M., An overview of polynomially computable characteristics of special interval matrices, Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications Studies in Computational Intelligence 835. Springer, Cham (2020), 295-310
[8] Monge, G., Mémoire sur la théorie des déblais et des remblais, De l’Imprimerie Royale, Paris (1781), French
[9] Tarjan, R. E., Edge-disjoint spanning trees and depth-first search, Acta Inf. 6 (1976), 171-185
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.