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