Grafy, hry, optimalizace, algoritmy, teoretická informatika

Zabýváme se diskrétní optimalizací. Zkoumáme složitost grafových a jiných problémů, herních mechanismů a kombinatorických her. Navrhujeme efektivní algoritmy. Využíváme prostředků klasické teorie složitosti, parametrizované složitosti, teorie grafů nebo například celočíselné lineární programování.

Aplikace

Navrhujeme přesné polynomiální, parametrizované a mírně exponenciální algoritmy, aproximační algoritmy či kombinatorické hry, jejichž ekvilibria představují efektivní řešení daného problému. Ukazujeme dolní meze pro časovou složitost algoritmu řešícího daný problém. Mezi výsledky naší výzkumné skupiny patří i čistě kombinatorické, tedy popisující vlastnosti objektů či vztahy mezi nimi, například z oblasti Ramseyovské teorie.

Problémy, kterými se zabýváme, jsou veškeré diskrétně modelované optimalizační úlohy. Jde o širokou škálu problémů – od grafových přes rozvrhovací či problémy z oblasti Social Choice až po strategie pro kombinatorické hry. V řadě algoritmů používáme výsledky týkající se celočíselného lineárního programování.

Čemu se skupina věnuje?

Kde nás najdete?

Výzkumná skupina Grafy, hry, optimalizace, algoritmy, teoretická informatika
Katedra teoretické informatiky
Fakulta informačních technologií
České vysoké učení technické v Praze

Budova A, 12. patro
Thákurova 7
Praha 6 – Dejvice
160 00

Kontaktní osoba

RNDr. Ondřej Suchý, Ph.D.

Za obsah stránky zodpovídá: doc. Ing. Štěpán Starosta, Ph.D.