A korábbi posztban megkezdett felsorolást folytatom.
3. Online hipergráfszínezés. Ez valójában több probléma, mivel a gráfszínezés kiterjesztése hipergráfokra többféleképp lehetséges. Itt minden esetben az input a hipergráf, amelynek csúcsait kell színezni úgy, hogy az eddig látott csúcsok által feszített részhipergráfot látjuk, és cél a felhasznált színek számának minimalizálása. Az elutasítás itt az aktuális csúcs eldobása a hipergráfból. Színezés hipergráfok esetében többféle van, innen a több probléma.
(a) Tarka színezés. Ekkor minden élet úgy kell színezni, hogy ne legyenek benne egyszínű csúcsok. Ez valójában a gráfszínezés egy speciális gráfosztályra, hiszen a hipergráf éleire egy-egy klikket teszünk. Az általános gráfszínezési eredményeknél jobbat nem ismerek, nem tudok olyan eredményről, amely erre az osztályra vonatkozik. Így először ennek az elutasítás nélküli változatát érdemes nézni, mielőtt nekiesünk az elutasításosnak. Hajrá!
(b) "Conflict free" színezés. Itt úgy kell színezni a csúcsokat, hogy minden élben legyen olyan csúcs, amelynek a színe abban az élben egyedi, azaz ott már nincs másik ugyanolyan színű csúcs. Ez egy érdekes modell, a motivációja rádióadók frekvenciájával van összefüggésben, ahol cél minden tartományban, hogy legyen egyedi frekvenciájú torony. (Természetesen a tarka színezés is "conflict free".) Az elutasítás nélküli változatot néhány speciális hipergráfosztály esetén vizsgálták (pl. intervallumok), tehát ott is vannak fehér foltok.
(c) A harmadik típusú színezés, amelynek nem ismerem jelzőjét, az, ahol nem lehetnek egyszínű élek. Ennek elutasítás nélküli változatát Imreh Csanáddal vizsgáltuk, már 2-színezhető hipergráfra is reménytelenül sok szín is kikényszeríthető. Ennek ellenére esetleg érdemes lehet megnézni mégis az elutasításos változatot is, terveim között szerepel is, lehet, hogy legközelebb erről írok...
4. Online klaszterezés. Utoljára maradt - hacsak nem bővítem később a listát - ez a problémakör, amely szintén szerepel a nem túl hosszú távú terveim között. Az online klaszterezés célja egy metrikus tér pontjainak valamilyen feltételnek eleget tevő csoportokba sorolása, a minimalizálandó célfüggvény általában a csoportok (klaszterek száma), plusz mérete. Rengetek modell létezik, mivel sokféle metrikus tér van, és a feltételek, illetve célfüggvények is többfélék lehetnek: fix (1) méretű vagy változtatható méretű, rögzített vagy nem rögzített középpontú klasztereket hozunk-e létre az eljárás során. Itt is teljesül, hogy még az elutasítás nélküli esetben is sok a nyitott kérdés, bár az egydimenziós euklideszi tér már lerágott csont - de nem az elutasításos változata ;).
