Diplomová práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Matroid Based Approach to Matrix Sparsification

Bc. Kristýna Pekárková
Anotace

Celočíselného programování je jednou z nejvýznamnějších oblastí diskrétní optimalizace. Je známo, že tento problém je výpočetně těžký, výzkum se tedy soustředí na hledání vstupních instancí, na kterých je celočíselné programování efektivně řešitelné. Koutecký, Levin and Onn [ICALP'18] dokázali, že celočíselné programování je parametrizovatelné duální stromovou hloubkou a složitostí prvků matice. Tato …více

Abstract

Integer programming is an important problem in discrete optimization. As it is known to be computationally hard in general, significant attention has been paid to finding instances that can be solved efficiently. Koutecký, Levin and Onn [ICALP'18] proved that integer programming is fixed parameter tractable when parameterized by the constraint matrix dual tree-depth and the entry complexity. However …více

Klíčová slova
graphs matroids combinatorics combinatorial optimization integer programming parameterized complexity fixed parameter tractability tree-depth branch-depth
Zadání práce
Koutecký, Levin and Onn [ICALP'18] proved that integer programming is fixed-parameter tractable when parameterized by the dual tree-depth of the constraint matrix and the entry complexity. The aim of this thesis is to investigate a possible use of matroid tools to find matrices with small dual tree-depth row-equivalent to the input constraint matrix and seek applications in combinatorial optimization, in particular, in integer programming.
Administrativní informace
Práce zkontrolována:
19. 5. 2021 01:20, prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Plný text práce
650,6 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
21. 6. 2021
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Daniel Kráľ, Ph.D., DSc.
KTP FI MU

Oponent

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Principy programovacích jazyků

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.