Stránka 1 z 1

Mat. prog. a polyedr. komb. - Kolman, Löebl

Napsal: 8. 2. 2017 10:19
od Erim
Na Zkoušce u pana Kolmana jsem byl sám a chtěl nějaké srovnání probraných algoritmů (elipsoidová metoda a metoda vnitřního bodu) a na příkladu minimální kostry ukázat, že elipsoidová metoda může být polynomiální v počtu proměnných, přestože je zápis lineárního programu exponenciální.

Na Zkoušce u pana Löebla jsme byli čtyři, každému zadal dvě otázky se slovy, že kompletní řešení by mělo být na papíře. Potom, když si nás začal procházet a číst si naše řešení, občas položil nějaké doplňující otázky. Otázky byly:
1) Hladový algoritmus včetně důkazu že funguje právě na matroidech. Chtěl k tomu ekvivalenci s LP nad polyedrem {z : pro každé A subset X, z(A) <= r(A)}. Jako doplňující otázku chtěl dokázat, že se ten polyedr rovná přesně konvexnímu obalu charakteristických vektorů nezávislých množin.
2) Průnik dvou matroidů. Tady mu stačilo povídání o maximalizaci, minimaxovou dualitu, že je to v NP i co-NP, příklad a že existuje efektivní algoritmus. K tomu minimaxu chtěl ještě dokázat alespoň jednu z nerovností.
3) Duální matroidy a jejich vztah ke grafovým matroidům. Když to četl, tak se pozastavil jen u důkazu, že duál matroidu je opravdu matroid, všechno ostatní, včetně důkazu že G rovinný právě když duál M_G je grafový, jen přelétl pohledem.
4) Matroidové operace a jednoduché matroidy řádu 3. Ptal se jen na důkaz toho, že duál matroidu je matroid.