Monge property for interval matrices

• Thesis title in Czech: Mongeova vlastnost pro intervalové matice
• Thesis title in English: Monge property for interval matrices
• Key words: Intervalová analýza, Silná Mongeovost, Slabá Mongeovost, Problém obchodního cestujícího
• English key words: Interval analysis, Strong Monge, Weak Monge, Travelling salesman problem
• Academic year of topic announcement: 2018/2019
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: prof. Mgr. Milan Hladík, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 30.10.2018
• Date of assignment: 30.10.2018
• Confirmed by Study dept. on: 06.11.2018
• Date and time of defence: 27.06.2019 09:00
• Date of electronic submission: 16.05.2019
• Date of submission of printed version: 17.05.2019
• Date of proceeded defence: 27.06.2019
• Opponents: prof. RNDr. Karel Zimmermann, DrSc.

Guidelines

- Vyjádření různých podmínek pro silnou Mongeovu vlastnost intervalové matice
- Volitelně podmínky pro slabou Mongeovu vlastnost intervalové matice
- Analýza algoritmických aspektů výše zmíněných podmínek
- Analýza operací zachovávajících Mongeovu vlastnost intervalové matice
- Prozkoumání použití pro optimalizační úlohy s nepřesnými daty

References

[1] R.E. Burkard, B. Klinz, R. Rudolf, Perspectives of Monge properties in optimization, Discrete Appl. Math., 70, 95-161, 1996.
[2] M. Fiedler. Remarks on Monge matrices. Mathematica Bohemica, 127(1), 27-32, 2002.
[3] M. Fiedler et al., eds., Linear Optimization Problems with Inexact Data, Springer, New York, 2006.
[4] M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.

Preliminary scope of work

Mongeova matice je definovaná jednoduchou podmínkou a hraje důležitou roli v několika problémech. Například v dopravních úlohách charakterizuje velice efektivně řešitelné případy. Cílem práce je zobecnit tyto matice na intervalové v silném smyslu (všechny jsou Mongeovy) a slabém smyslu (aspoň jedna je Mongeova). Bude nás zajímat charakterizace těchto vlastností, jejich složitost a postačující/nutné podmínky.