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.

Decemberi terméketlenség

Előző hónap eleje óta nem volt új poszt, ennek több oka van. Vagyis egy: nem történt semmi. Aztán arra gondoltam, hogy mégis meg kell írni ezt. Mármint hogy nem történt semmi. Merthogy a matematikai kutatásban ez előfordul, hogy nem halad előre. És ugyan kevés idő jutott a kutatásra a szorgalmi időszak hajrája, a vizsgaidőszak kezdete és az ünnepek miatt, mégsem ez a fő ok. Hanem az, hogy néha hiába számol az ember, nem jön ki, amit szeretne. Sőt, nem jön ki semmi. Itt is ez történt. Kitalálok egy algoritmust (online színezéses probléma), próbálom elemezni. Első nekifutásra nem jön ki semmi értelmes versenyképességi hányados. Próbálom máshogy, ez sem jön ki. A harmadik megközelítés sem jobb. Ekkor váltok, felfrissülésképp alsó korlátot próbálok bizonyítani, de nem jön ki a triviális 1 korlátnál jobb (ugye minden online algoritmus legalább 1-versenyképes). Próbálom máshogy, az sem jó. Visszatérek a másik oldalra, kitalálok egy másik algoritmust, azt próbálom elemezni, és így tovább... Ezt ismételtem 3-4-szer (természetesen több nap ment rá), majd feladtam. Egy időre. Ilyenkor néha hasznos, ha pihentetjük a témát egy kicsit, majd később elővesszük, hátha addigra leülepszik bennünk a probléma és új ötletünk támad. Addig meg csinálunk valami mást. Például sorra vesszük a nyitott problémákat, hátha találunk köztük egy szimpatikusat. Később, ha visszatérek rá, beszámolok az eredményről.