Konferenciára készülve

Beérett az első gyümölcse a legutóbbi, színezéssel kapcsolatos munkának, amiről egy korábbi posztban írtam. A héten konferenciára megyek, ott fogom előadni egyelőre a full edge modellben elért eredményeket (az összes eddigi eredmény egy cikkben is benne lesz, ez egyelőre folyamatban van). Ezeket egy absztraktban foglaltam össze, amit már a konferenciára jelentkezéskor el kellett küldeni. A konferencia hallgatóknak és PhD hallgatóknak lesz szervezve, de előadnak rajta fiatal kutatók is. Ez megint olyan típusú konferencia, amely nem szűk téma köré szerveződik (erről korábbi posztban írtam). A célja az egymással és egymás témájával való ismerkedés. Másrészt azért is különleges ez a konferencia, mert két oldalát látom: azon túl, hogy előadok rajta, szervezője is vagyok. Érdekes belelátni a részletekbe és nehézségekbe, amikkel egy konferencia szervezése jár. De mivel ez már messze esik a blog témájától, talán máshol, máskor írok róla.
Az előadás 25 perces lesz, plusz 5 percet hagynak az előadás utáni kérdéseknek. Ez kicsit hosszú, általában (legalábbis a saját mintavételezésem alapján) kevesebb időt adnak, ami nem nagyon teszi lehetővé a részletekbe menő előadást. Itt viszont lehetőség van néhány, de természetesen nem minden finomság megmutatására, ami elgondolkodtat, hogy miből mennyit és hogyan mondjak el. Csökkenti a szabadságfokot, hogy nem a szűk szakterület képviselőinek fogok beszélni, így részletesebb bevezetőre lesz szükség, hogy értsék, miről beszélek. Így már nem is jut olyan sok idő a tényleges eredményekre. De még így is belefér egy rövid bizonyítás és egy ábrán szemléltetett bizonyítás vázlat. De leginkább csak a fő eredmények felsorolására van idő. Azt szokták mondani, hogy minden előadásba kell egy bizonyítás és egy vicc, és fontos, hogy a kettőt meg lehessen különböztetni. Hozzátenném ehhez, hogy hasznos, ha az előadás szemléletes, és segíti a figyelem fenntartását, ha az egész előadás humoros, vagy legalábbis nem csak egy vicc van benne (az enyémre ez utóbbi nem fog teljesülni, remélem, az előbbi igen). Mostanában az előadásokat nem táblán tartják és az írásvetítő is elvétve kerül elő már (bár hasznos azon IS kivetíteni a definíciókat, hogy folyamatosan szem előtt legyenek, segítve a megértést), hanem diákat csinálnak, általában pdf vagy ppt formátumban. A matematikusok a latexben beamer csomag használatával generált pdf-et preferálják, én is ezt teszem. Az előadásfóliák már elkészültek, most átgondolom, melyiknél mit fogok mondani. Erre azért van szükségem, mert még nem sok ilyenfajta előadást tartottam, nagyobb gyakorlattal, ezt már nem szokták megtenni, sőt, a tapasztaltabbak a diákat is a helyszínen dobják össze nem sokkal az előadásuk előtt ;)
A konferencia után jelentkezek egy beszámolóval, utána rátérek a következő témára.

Színezzünk!

Három hónap szabadság után lássuk, hol is tartunk.

Legutóbbi nyitott problémákkal foglalkozó bejegyzésben írtam hipergráfszínezésről is. Itt is erről lesz szó, de ezennel csökkenteni fogom a nyitott kérdések számát olyanok megválaszolásával, amelyeket a közelmúltban sikerült megoldani (nem megyek részletekbe, mivel ezek publikálatlan eredmények egyelőre). Nyugalom, azért marad bőven még :)

Több modell lesz. A leírt színezések (tarka, conflict-free és a nem egyszínű) rögtön háromszorozzák ezek számát. Az egyik megközelítés, amelyet mi vizsgáltunk, azt feltételezi, hogy egy élet csak akkor látunk meg, ha minden csúcsa megérkezett, előtte semmilyen információnk nincs róla. Lehet más modelleket is definiálni (és mivel ezeket nem vizsgálták, mégiscsak bővítem a nyitott problémák körét), amelyben egy él nyomát látjuk az eddig érkezett csúcsok halmazán, esetleg tudjuk az adott élről, hogy minden csúcsa megérkezett-e már (ez így már több információ, mint amit a mi modellünkben az algoritmus kap).

Eddig még nem volt szó elutasításról. Ha az is belép a képbe, akkor megint kétféle megközelítést vehetünk:
1. full edge (teljes él) modellnek nevezzük, ha csak azokat az éleket kell helyesen színezni (az adott színezés szerint), amelyeknek egyetlen csúcsát sem utasítottuk el. Ebben a modellben a nem egyszínű színezésbeli eredmény a legérdekesebb: azt mondja, általánosságban nem lesz lényegesen több a versenyképességi hányados, mint az elutasítás nélküli esetben (n/2 felsőegészrésze). Miért érdekes ez? Mert általában rosszabb, legtöbbször egy 2-es szorzó jön be. A conflict-free színezésnél már más (az aszimptotikusan éles (n-1)/φ+1, ahol φ az aranymetszés arányszáma) korlát jött ki, mint az elutasítás nélküli esetnél, a tarkával pedig nem foglalkoztunk, mivel nem tűnt érdekesnek, gondoljuk csak meg: minden online tarka színező algoritmus úgy működik, hogy nem használja kétszer ugyanazt a színt.

2. trace (nyom) modellnek nevezzük, ha minden élnek az elfogadott csúcsokon vett nyomáról követeljük meg, hogy helyesen legyenek színezve. A modell érdekessége, hogy az előzővel ellentétben itt ha valamelyik színt kétszer használja az algoritmus, akkor a további csúcsok elfogadására kényszeríthető. Másik érdekesség, hogy itt együtt tudtuk kezelni a nem egyszínű és a conflict-free színezést, azonos (aszimptotikusan éles) korlát ((n-2)/φ+2) jött ki. Tarka színezéssel itt sem foglalkoztunk.

Rengeteg nyitott kérdés maradt az általunk vizsgált modellekben (pl. speciális hipergráfosztályokra vonatkozó korlátok), hát még azokban, amiket nem vizsgáltunk!

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.