Informace o projektu
Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
| Kód projektu | GA14-03501S CEP CORDIS MU WEB INET MU |
|---|---|
| Doba řešení | 01.01.2014–31.12.2016 |
| Stav | ukončený |
| Investor | Grantová agentura ČR |
| Program | Standardní projekty |
| Řešitel za FI | |
| Členové realizačního týmu za FI |
Anotace
Jeden z možných přístupů ke zdolání zdánlivě nepřekonatelné překážky NP-těžkosti algoritmických problémů nám podává teorie
parametrizované složitosti: Vstup těžkého problému je opatřen doplňkovým parametrem - libovolným číslem k, jehož jakákoliv počitatelná
funkce omezuje výpočetní složitost našeho problému. Snahou je volit parametr k tak, aby jeho hodnota byla na zajímavých vstupech nízká,
což následně umožňuje efektivní řešení problémů na takto charakterizovaných vstupech. V projektu budou hledány a studovány vhodné
strukturální a geometrické parametry pro třídy kombinatorických objektů (grafů) a nové poznatky budou využity v návrhu lepších
parametrizovaných algoritmů a obecných logikou popsaných tzv. algoritmických metavět. Mimo jiné bude pokračovat nedávno velmi úspěšné
nalézání dolních mezí parametrizované řešitelnosti problémů. Mezi novými směry výzkumu v navržené oblasti jsou především zmíněny
oblasti metavět pro kernelizaci (efektivní parametrické předzpracování) problémů a využití geometrických parametrů (vycházejících například
z reprezentace vstupního grafu).
parametrizované složitosti: Vstup těžkého problému je opatřen doplňkovým parametrem - libovolným číslem k, jehož jakákoliv počitatelná
funkce omezuje výpočetní složitost našeho problému. Snahou je volit parametr k tak, aby jeho hodnota byla na zajímavých vstupech nízká,
což následně umožňuje efektivní řešení problémů na takto charakterizovaných vstupech. V projektu budou hledány a studovány vhodné
strukturální a geometrické parametry pro třídy kombinatorických objektů (grafů) a nové poznatky budou využity v návrhu lepších
parametrizovaných algoritmů a obecných logikou popsaných tzv. algoritmických metavět. Mimo jiné bude pokračovat nedávno velmi úspěšné
nalézání dolních mezí parametrizované řešitelnosti problémů. Mezi novými směry výzkumu v navržené oblasti jsou především zmíněny
oblasti metavět pro kernelizaci (efektivní parametrické předzpracování) problémů a využití geometrických parametrů (vycházejících například
z reprezentace vstupního grafu).