| Title:
|
Interval matrices with Monge property (English) |
| Author:
|
Černý, Martin |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
65 |
| Issue:
|
5 |
| Year:
|
2020 |
| Pages:
|
619-643 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
Monge matrix |
| Keyword:
|
interval matrix |
| Keyword:
|
interval analysis |
| Keyword:
|
linear programming |
| MSC:
|
65G99 |
| MSC:
|
90C05 |
| idZBL:
|
07285949 |
| idMR:
|
MR4160785 |
| DOI:
|
10.21136/AM.2020.0370-19 |
| . |
| Date available:
|
2020-09-23T13:49:27Z |
| Last updated:
|
2022-11-07 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148369 |
| . |
| Reference:
|
[1] Alefeld, G., Mayer, G.: Interval analysis: Theory and applications.J. Comput. Appl. Math. 121 (2000), 421-464. Zbl 0995.65056, MR 1780057, 10.1016/S0377-0427(00)00342-3 |
| Reference:
|
[2] Burkard, R. E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization.Discrete Appl. Math. 70 (1996), 95-161. Zbl 0856.90091, MR 1403225, 10.1016/0166-218X(95)00103-X |
| Reference:
|
[3] Cechlárová, K., Szabó, P.: On the Monge property of matrices.Discrete Math. 81 (1990), 123-128. Zbl 0726.06010, MR 1054969, 10.1016/0012-365X(90)90143-6 |
| Reference:
|
[4] Deineko, V. G., Filonenko, V. L.: On the reconstruction of specially structured matrices.Aktualnyje problemy EVM i programmirovanije. Dnepropetrovsk, DGU (1979), Russian. |
| Reference:
|
[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 |
| Reference:
|
[6] Greenlaw, R., Hoover, H. J., Ruzzo, W. L.: Limits to Parallel Computation: $P$-Completeness Theory.Oxford University Press, Oxford (1995). Zbl 0829.68068, MR 1333600 |
| Reference:
|
[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. 10.1007/978-3-030-31041-7_16 |
| Reference:
|
[8] Monge, G.: Mémoire sur la théorie des déblais et des remblais.De l'Imprimerie Royale, Paris (1781), French. |
| Reference:
|
[9] Tarjan, R. E.: Edge-disjoint spanning trees and depth-first search.Acta Inf. 6 (1976), 171-185. Zbl 0307.05104, MR 0424598, 10.1007/BF00268499 |
| . |
