Čemu se skupina věnuje?
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í.
