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: P -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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.