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.

Nyitott probémák II.

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 ;).

Beszámoló egy konferenciáról

Megint egy kis kitérő a nyitott problémák folytatása előtt (hamarosan az is elkövetkezik). A Szegedi Tudományegyetem Bolyai Intézete júliusban konferenciát szervezett Krámli András 70. születésnapjának tiszteletére, erről szeretnék most egy rövid összefoglalót írni.

De előtte essen pár szó általában a konferenciákról. Az általam eddig látott szakmai konferenciákat két kategóriába sorolnám: az egyik szűkebb témájú, kifejezetten azon a szakterületen jártas kutatóknak szól, és a terület legfrissebb eredményeit igyekszik bemutatni. Ez azért hasznos, mert témánk legaktuálisabb eredményei tekintetében folyamatosan képben lehetünk. Ilyen konferenciákat szoktunk gyakrabban látogatni, saját friss eredményeinket is ilyeneken osztjuk meg kutatótársainkkal. A másik kategória, amelybe a fent említett is tartozik, általában tágabb területeket ölel fel, nem feltétlenül ismeretlen új eredményeket ismertet, hanem sokszor egy-egy témakört jobban átfogó, nem csak a szűk szakterülettel foglalkozó kutatóknak szóló előadások hangzanak el. Miért lehet hasznos egy ilyen konferencia? Hiszen a szakterület művelői nem biztos, hogy sok újat hallanak, akik más témákkal foglalkoznak, azok számára nem biztos, hogy érdekesek lehetnek az ott elhangzottak. Legalábbis első pillanatban ezt gondolhatjuk. Mégis érdemes időnként ilyen konferenciákon is részt venni. Ha a szakterületünkön belüli a téma, akkor hallhatunk olyan előadásokat, amelyek jól összefoglalják, esetleg más szemszögből tálalják az esetleg már általunk ismert eredményeket (amikbe azért keveredhetnek újak is), ha más területen dolgozunk, akkor is tanulhatunk érdekes, hasznos módszereket, technikákat, amelyekkel megújíthatjuk saját kutatási területünket, esetleg rég parlagon fekvő problémákat más szemszögből tudunk megközelíteni ezáltal. És nem utolsó sorban a konferenciák a kapcsolatépítésről is szólnak, ezeken (főként a második típusú) a konferenciákon megismerhetünk olyan kutatókat is, akik nem szorosan a mi témánkkal foglalkozik, mégis érdemes lehet vele együtt dolgozni.

Ezek után lássuk a júliusi konferencia tanulságait. A konferencia angol nyelvű (mint a legtöbb szakmai konferencia, ahol nem csak magyar résztvevők vannak) és sztochasztikus témájú volt, amely nem áll túl közel az algoritmikus és kombinatorikus témákhoz, amelyekkel foglalkozom, de nem is teljesen idegen, hiszen az algoritmusok és a kombinatorika területén belül lépten-nyomon beleütközhetünk a véletlen fogalmába, és ekkor nagyon hasznosak lehetnek a sztochasztikus területeken kidolgozott módszerek.

A konferencia előadói Krámli András témavezetője (Yakov Grigorevich Sinai, aki kétségtelenül figyelemfelkelő és érdekes előadást tartott), kollégái és tanítványai voltak, előadásaik olyan témák köré csoportosultak, amelyek jelentősek András munkásságában, illetve közös munkájukban. Az előadások sokszínűsége jellemző az ilyen konferenciákra, így nem tudok, és nem is szeretnék minden témára kitérni. Nem célom absztraktokat sem felsorolni az előadásokról, inkább azt veszem sorra, mit profitáltam a prezentációkból, a teljesség igénye nélkül. Természetesen nem várható, hogy minden előadás hasznos legyen a konkrét kutatási témám szempontjából, viszont a látókörömet tágítják, ez mindenképp előnyömre válhat. Az elhangzott előadások témái közül több is kombinatorikai jellegű, ilyenek voltak például a perkolációval (nagy véletlen gráfok összefüggő részgráfjait vizsgáló terület) foglalkozók (Pete Gábor és Balogh József prezentációi). Ezek kombinatorikai szempontból érdekes előadások, viszont a téma jellegénél fogva a technikák kissé távol állnak az online algoritmusok témakörében alkalmazottaktól. A kevésbé kombinatorikai jellegű témákról még inkább gondolhatnánk ezt, de nem feltétlen van így: ha véletlen modellt tekintünk (ahol az online algoritmus véletlen döntéseket is hozhat), akkor igen hasznosak lehetnek a sztochasztikában (pl. véletlen folyamatok vizsgálatában) alkalmazott módszerek.

Talán a számomra leghasznosabb előadások Erdős Lászlóé és Tóth Bálinté voltak. Előbbi véletlen mátrixok sajátértékeiről szólt. A véletlen mátrixok vizsgálata fontos eszköze a kombinatorikának, sajátértékeinek vizsgálata kétségtelenül hasznos technika, amelybe bepillantást engedett ez az előadás. Mátrixokról - bár egészen más megközelítésben - beszélt Bolla Marianna is, az ő előadásában is fellelhetőek voltak a kombinatorikában jól használható eszközök.
Tóth Bálint divergenciamentes környezetben vett véletlen sétákról beszélt. Az előadáson ismertetett technikák természetesen nem közvetlenül alkalmazhatóak az online algoritmusok témakörében, megfelelő módosításokat kell eszközölni, hogy átültethessük oda, csak meg kell találni az analógiát a két problémakör között és a módját, hogy a véletlen séta "lépéseit" hogyan fordítsuk át az algoritmus lépéseivé.
Talán hasznos lehet még Szepesvári Csaba előadása, amely az "online-to-con fidence-set conversion" nevű, bizonyos típusú online tanuló algoritmusok vizsgálatában alkalmazható technikáról szólt, bár közvetlen alkalmazhatóságát még nem látom az általam vizsgált kérdésekben, de a jövőben ez változhat.

Nyitott problémák I.

Ennyi felvezetés után itt az ideje olyan nyitott kérdéseket nézni, amelyeket érdemes lehet vizsgálni (nem garantálom, hogy az, hiszen a kérdések nyitottak, vizsgálatuk nem vezet feltétlen eget verően érdekes eredményekre).
Ezen a területen olyan nyitott problémákat szokás vizsgálni, amelyek nem elutasításos változata már eléggé feltárt terület, különben általában az elutasítás nélküli változatnak esnek neki (kivétel lehet olyan terület, amely elutasításos változata gyakorlatilag jobban motivált, de ilyenbe még nem botlottam). A felsorolt problémák sem időrendet, sem másmilyen logikai sorrendet nem fognak követni, úgy írom le, ahogy eszembe jutnak. Nem lesz teljes a lista, azon problémaköröket érinti, amelyek foglalkoztatnak.

1. gráfszínezés. Az online gráfszínezésnek kiterjedt irodalma van, a régebbi eredményeket a
H. A. Kierstead, Coloring Graphs On-line, Online algorithms: The State of the Art (A. Fiat, and G. J. Woeginger (eds.)), Vol. 1442 of Lecture Notes in Computer Science, Springer-Verlag Berlin, Heidelberg, 281–305, 1998. összefoglaló cikkben olvashatjuk.
Az eredeti online modellben a gráf csúcsai érkeznek egyesével, az eddig érkezett csúcsok által feszített részgráfot látjuk, így kell az új csúcsot színezni. A költség a felhasznált színek száma. Az elutasításos változatban minden csúcshoz tartozik egy büntetés is, amit akkor fizetünk, ha azt a csúcsot nem színezzük. Ez a büntetés hozzáadódik a költséghez. Már a büntetés nélküli változatra is igaz, hogy nincs konstans versenyképes algoritmus, így speciális gráfosztályokat szoktak vizsgálni. Tehát az elutasításos esetben sem lesz (nyilvánvalóan az elutasítás nélküli alsó korlátok az elutasításos esetre is érvényesek), és érdemes megvizsgálni ugyanazokat gráfosztályokat (esetleg újakat).

2. lista színezés. Ez a probléma kilóg a sorból. Valójában már az is kérdéses, hogy hogyan definiálható az elutasításos változat, vagy van-e értelme, ráadásul az eredeti problémakörben is sok nyitott kérdés van, tehát a kutatást az elutasítás nélküli változattal érdemes kezdeni, ami szerintem szintén érdekes. Az online gráfszínezéssel összevetve ez egy furcsa modell. Itt előre ismerjük a gráfot, és nem a csúcsokat, hanem a színeket kapjuk, minden lépésben azon csúcsok felsorolásával, amelyek azzal a színnel színezhetők, és meg kell mondani, mely csúcsok kapják majd ténylegesen azt a színt (helyes színezést kell itt is kapjunk). A modellt a színező és ellenfele közti játékkal szokták megfogalmazni: a színező ellenfele adja az inputot, a színező választja ki az adott színűre színezendő csúcsokat. A játékhoz adott egy csúcsokon értelmezett f függvény, amely természetes számokat rendel a csúcsokhoz. A színező veszít, ha van olyan v csúcs, amelyet már f(v)-szer kapott, de nem színezett ki. A gráf online f-choosable, ha van a színezőnek nyerő stratégiája. Az online choise number a legkisebb k, amelyre a gráf k-choosable, azaz f-choosable az f azonosan k konstans függvénnyel. Kevés eredmény van a területen, ezek is csak azokat a gráfokat szeretnék karakterizálni (eddig viszonylag nem sok sikerrel), amelyek online choise number-ük megegyezik a kromatikus számukkal.
Mi lenne itt az elutasításos változat (már ha eljutunk annak vizsgálatáig)?

folyt. köv.

Hogyan fogjunk neki?

Általában ha egy meglévő modellt módosítunk új eredmények reményében (hiszen ezzel nyitottunk egy új szűz területet), megvizsgáljuk, hogy miben hasonlít és miben tér el az eredeti modelltől.
Ha túlzottan hasonlít és minden eredmény szinte egy az egyben átvihető, akkor félő, hogy a szakmai társadalom önmagában nem túl érdekesnek minősíti, és nem fogjuk tudni publikálni.
Ha túlzottan eltér, akkor technikai szempontból nem lesz sok köze az eredetéhez, és nyitunk egy olyan új problémakört, aminek az eszközeit teljes egészében ki kell dolgozni, ennek az a kockázata, hogy nem sikerül, és ha ez sok idő és energia beleölése után derül ki, az a jelenlegi publikációs kényszer mellett gondokat okozhat kutatói pályafutásunkban.
Tehát a két véglet között szeretnénk maradni. Ha találtunk ilyet (pl. a k-szerver probléma ilyen volt), akkor megnézzük, mi alkalmazható az eredeti modell vizsgálatából, ami nem működik, miért, és lehetne-e módosítani valahogy, hogy működjön. A k-szerver probléma esetén a legígéretesebb algoritmus a WFA (munkafüggvény algoritmus), amely elemzése az ún. potenciálfüggvény technikával megy. A technika az elutasításos változatban is alkalmazható, a számolásokon annyit kellett változtatni, hogy néhány újabb aleset vizsgálatát kellett nézni a bonyolultabb modell miatt, viszont az újabb esetek vizsgálata nem volt sokkal nehezebb, mint az eredetieké, viszont kicsit máshogy kellett kezelni. Ez, és a probléma motivációja (ti. a való életben is reálisabb modellnek látszik, hogy kéréseket vissza is utasíthatunk) már elég érdekessé tették az eredményt, hogy ne kapjunk rá elutasító véleményt. Így remélhetőleg hamarosan megint születik egy új publikáció :)

adminisztrációs kitérő

Azt ígértem, a következő poszt arról szól, hogyan állunk neki egy olyan típusú problémának, mint amilyenről az előző bejegyzésben volt szó. Időközben adminisztrációs feladatok jöttek, azokkal kellett foglalkoznom, így mivel manapság már ez is része a kutatómunkának, meg kell emlékeznem erről is, az ígéret pedig egy poszttal tovább csúszik (de időben remélhetőleg nem sokat).
Mostanában a kutatások finanszírozása pályázatokon keresztül valósul meg, ezek egy jelentős része európai uniós pénz. Az ilyen pályázatoknak egyre szövevényesebb bürokratikus háttere van, amely egyre több adminisztrációval jár, ami sajnos épp a hasznos kutatástól veszi el az időt. Kutatási terveket és beszámolókat kell írni, utazáskor, eszközbeszerzéskor, stb. minden szóbajövő költségről megfelelő formájú igazolásokat felmutatni. Aki gyakran pályázik, az persze ezekben jártas lesz és egyre kevesebb időt vesz igénybe (ez igaz a kutatással kapcsolatos más tevékenységekre is, pl. szakirodalmazás), feltéve, hogy nem bonyolítják tovább az így is terjedelmes adminisztrációt.