LH12095 NewAlgo

Nové kombinatorické algoritmy – rozklady instancí, parametry úloh a jejich efektivní řešení

Zahraniční partneři

O projektu

Projekt je zaměřený na základní výzkum na rozhraní teoretické informatiky a diskrétní matematiky.

Vzhledem k tomu, že řada úloh kombinatorické optimalizace není řešitelná efektivně v plné obecnosti — dle paradigmatu polynomiální řešitelnosti patří mezi NP-těžké úlohy — je třeba při návrhu algoritmů zkoumat dodatečné podmínky a jejich vliv na možnosti existence efektivního řešení těchto úloh.

Od 70. let minulého století byla navržena řada metod pro zkoumání těchto problémů. Cílem projektu je blíže prozkoumat a rozvinout metody objevené zejména v posledních pěti letech, např. tzv. parametrizovanou složitost, strukturální složitost a tzv. rychlé přesné exponenciální algoritmy.

Aktuality

Během konference Prague Midsummer Combinatorial workshop se ve dnech 31.7. a 2.8.2012 uskutečnil kick-off meeting projektu. Domácí účastníci zde před mezinárodním publikem představili cíle projektu formou odborných přednášek: