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.