Nagy-György Judit: Online színezések tanácsadói bonyolultsága

Az online gráfszínezési problémában az algoritmus a gráfot csúcsonként kapja, a kapott csúcsok által feszített részgráf ismeretében kell a csúcsot színezni. Nemrégiben kezdték el vizsgálni azt a kérdést, hogy ha van egy mindentudó orákulumunk, akkor a különböző modellekben hány bitet kell megsúgnia az online algoritmusnak, hogy az elérje az optimális célfüggvényértéket, általánosabban pedig egy konkrét versenyképességi hányadost.