Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
Monge matrix; interval matrix; interval analysis; linear programming
Monge matrix; interval matrix; interval analysis; linear programming
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.
References:
[1] Alefeld, G., Mayer, G.: Interval analysis: Theory and applications. J. Comput. Appl. Math. 121 (2000), 421-464. DOI 10.1016/S0377-0427(00)00342-3 | MR 1780057 | Zbl 0995.65056
[2] Burkard, R. E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discrete Appl. Math. 70 (1996), 95-161. DOI 10.1016/0166-218X(95)00103-X | MR 1403225 | Zbl 0856.90091
[3] Cechlárová, K., Szabó, P.: On the Monge property of matrices. Discrete Math. 81 (1990), 123-128. DOI 10.1016/0012-365X(90)90143-6 | MR 1054969 | Zbl 0726.06010
[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. MR 3451674
[6] Greenlaw, R., Hoover, H. J., Ruzzo, W. L.: Limits to Parallel Computation: $P$-Completeness Theory. Oxford University Press, Oxford (1995). MR 1333600 | Zbl 0829.68068
[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. DOI 10.1007/978-3-030-31041-7_16
[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. DOI 10.1007/BF00268499 | MR 0424598 | Zbl 0307.05104
Search
Partner of
