Interval matrices with Monge property

Martin Černý

Applications of Mathematics (2020)

  • Volume: 65, Issue: 5, page 619-643
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Černý, Martin. "Interval matrices with Monge property." Applications of Mathematics 65.5 (2020): 619-643. <http://eudml.org/doc/297231>.

@article{Černý2020,
abstract = {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.},
author = {Černý, Martin},
journal = {Applications of Mathematics},
keywords = {Monge matrix; interval matrix; interval analysis; linear programming},
language = {eng},
number = {5},
pages = {619-643},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Interval matrices with Monge property},
url = {http://eudml.org/doc/297231},
volume = {65},
year = {2020},
}

TY - JOUR
AU - Černý, Martin
TI - Interval matrices with Monge property
JO - Applications of Mathematics
PY - 2020
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 5
SP - 619
EP - 643
AB - 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.
LA - eng
KW - Monge matrix; interval matrix; interval analysis; linear programming
UR - http://eudml.org/doc/297231
ER -

References

top
  1. Alefeld, G., Mayer, G., 10.1016/S0377-0427(00)00342-3, J. Comput. Appl. Math. 121 (2000), 421-464. (2000) Zbl0995.65056MR1780057DOI10.1016/S0377-0427(00)00342-3
  2. Burkard, R. E., Klinz, B., Rudolf, R., 10.1016/0166-218X(95)00103-X, Discrete Appl. Math. 70 (1996), 95-161. (1996) Zbl0856.90091MR1403225DOI10.1016/0166-218X(95)00103-X
  3. Cechlárová, K., Szabó, P., 10.1016/0012-365X(90)90143-6, Discrete Math. 81 (1990), 123-128. (1990) Zbl0726.06010MR1054969DOI10.1016/0012-365X(90)90143-6
  4. Deineko, V. G., Filonenko, V. L., On the reconstruction of specially structured matrices, Aktualnyje problemy EVM i programmirovanije. Dnepropetrovsk, DGU (1979), Russian. (1979) 
  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. (2016) MR3451674
  6. Greenlaw, R., Hoover, H. J., Ruzzo, W. L., Limits to Parallel Computation: -Completeness Theory, Oxford University Press, Oxford (1995). (1995) Zbl0829.68068MR1333600
  7. Hladík, M., 10.1007/978-3-030-31041-7_16, Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications Studies in Computational Intelligence 835. Springer, Cham (2020), 295-310. (2020) DOI10.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. (1781) 
  9. Tarjan, R. E., 10.1007/BF00268499, Acta Inf. 6 (1976), 171-185. (1976) Zbl0307.05104MR0424598DOI10.1007/BF00268499

NotesEmbed ?

top

You must be logged in to post comments.