Eddig, mint a második posztban írtam, leginkább az online problémák elutasításos változatával foglalkoztam. Most felkeltette az érdeklődésemet az ún. advice complexity (nem ismerek rá magyar kifejezést). A fogalom a bonyolultságelméletből jön, az érdekli a kutatókat, hogy adott bonyolultsági osztályba mely problémák esnek ha kaphatnak plusz biteket, és mennyit az input hosszának függvényében (akinek ez zavaros, nézze meg a linket). Az online algoritmusokba is beemelhetjük a advice string fogalmát és megfogalmazhatunk olyan kérdéseket, hogy mennyi advice bit szükséges, hogy az online algoritmus elérje az optimális költséget, vagy adott c-re c-versenyképességet érjünk el. Approximációs sémákat is megfogalmaznak: tetszőleges ε esetén 1+ε versenyképességre törekednek minél kevesebb advice bit felhasználásával.
A modell önmagában is érdekes, bár sok kérdést már megoldottak benne (k-szerverre, ládapakolásra, ütemezésre, gráfszínezésre, stb., bár még bőven hagytak nyitva is), de ha kombináljuk meglévőekkel (pl. az elutasításos modellel), akkor lehetőségek széles skálájával találjuk szembe magunkat. Még mi sem tudjuk, hol kezdjük, ez a bőség zavara :)
Nincsenek megjegyzések:
Megjegyzés küldése