Gráfszínezés elutasítással

Új témába kellene kezdeni. Először -- amint erről már volt szó -- miután választottunk egy szimpatikus témát (színezés), megnézzük a szakirodalmat. Az, hogy mi a szimpatikus téma, a szakirodalom is meghatározza. Nem csak úgy, hogy az alapján ismerjük meg a kérdéseket és a technikákat, hanem azzal is, hogy látjuk, az általunk vizsgálni kívánt kérdést megoldotta-e valaki, ha nem, mekkora lépést tettek már meg a megoldás irányába. Például egy dolog, hogy kigondoltam, hogy az online klaszterezés elutasításos változatával szeretnék foglalkozni, de kiderült, hogy aminek épp nekiálltam volna, azt korábban valaki már kiszámolta. Így még mindig kevésbé fájdalmas, mint amikor már a kész cikket beküldve derül ez ki... Így hát elkanyarodtam a színezések felé, és ezek után ért a kellemes meglepetés: bár a gráfszínezés népszerű téma, ezen a területen még szinte szűz: csak egy eredmény van, Epstein és mtasi-é, amely szerint Δ+3-versenyképességet el lehet érni, de jobbat nem (Δ itt a gráf maximális foka). Az algoritmus ötlete egyszerű: amíg az összes eddigi büntetés el nem éri 1-et, elutasítunk mindent, utána pedig a mohó First Fit algoritmust futtatjuk büntetéstől függetlenül. Elsőre furcsa, de kicsit belegondolva természetes ötlet, ha nem szeretnénk, hogy az algoritmust nagyon be lehessen csapni. A másik alapötlet az elutasításos modellekben az lehet, hogy keresünk egy threshold értéket, az annál kisebb büntetésűeket elutasítjuk, a nagyobb büntetésűekre pedig valamilyen ügyes algoritmust alkalmazunk. Mivel sem gráfokra, sem hipergráfokra nincs még sok eredmény, viszont a terület eredménnyel kecsegtet, ennek érdemesebb nekivágni.