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.

Cikkírás rögös útjai

Nemrég küldtünk be újra egy cikket. Hogy miért újra? Egyáltalán hová is? Miért tettük? Kezdjük az elején.
Amikor a kutató elér egy tudományos eredményt, akkor azt a tudóstársadalom tudomására szeretné hozni (ezt el is várják). Ennek alapvetően két módja van: konferencián való ismertetés vagy szakfolyóiratban való megjelentetés. Mindkettőből vannak színvonalasak, kevésbé színvonalasak és kifogásolhatóak. Utóbbiakról most nem írnék. A színvonalat a bírálói rendszer biztosítja a közzététel mindkét formájában. Az ember beküldi az eredményét cikk formájában, majd egy vagy több bíráló elolvassa, véleményezi (általában névtelenül), konferencia esetén ez alapján elfogadják vagy elutasítják az adott rendezvényről az eredményt, folyóirat esetén árnyaltabb a dolog: elfogadják (accept), kisebb módosításokat javasolnak (minor revision), nagyobb módosításokat javasolnak (major revision) vagy elutasítják (reject). Az első eset első beküldéskor igen ritka folyóiratnál. Második és harmadik esetben módosítás után újra beküldi a kutató az eredményt (ebben a fázisban járunk, amire a poszt elején utaltam), ami alapján a bíráló(k) újabb vélemény(eke)t ír(nak), ez alapján újabb módosítás,... amíg végül el nem fogadják vagy el nem utasítják a cikket. Utóbbi esetben lehet próbálkozni más folyóirattal/konferenciával, és a kör kezdődik elölről.
Általában a kutatók nem szívesen beszélnek olyan munkájukról, ami éppen folyamatban van, és vagy még nincs eredmény, vagy a közelében vannak csak, vagy ha meg is van, még publikálatlan. Viszont ígértem, hogy konkrét problémáról fogok írni, az eredmények megvannak, és a bírálatok alapvetően pozitívak voltak, tehát nagy valószínűséggel a kért apróbb módosítások után már el fogják fogadni, ezért megosztom a kérdéseket, amelyek foglalkoztattak minket a kutatás során (és legközelebb remélhetőleg arról írok, hogyan lehet nekiállni ilyen és ehhez hasonló kérdésekhez).
Az alap kérdés a következő: vannak néhány (mondjuk k db) kiszolgálónk, ún. szerverek, ezek egy metrikus téren helyezkednek el (azaz van távolságfüggvényünk). Kérések jönnek sorban, amelyek a tér pontjai, és úgy kell kiszolgálni őket, hogy valamelyik szervert a kérés helyére mozgatjuk. A példa erre a tűzoltás szokott lenni, amikor valahol tűz üt ki, valamelyik tűzoltóállomásról odaküldenek egy kocsit. A példa ott sántít, hogy a tűzoltóautó dolga végeztével (vagy a ház leégése után) minden esetben visszamegy az állomásra, míg a mi esetünkben oda mehet és ott is maradhat a kiszolgáló, ahol neki tetszik. A cél a költség, azaz a kiszolgálók által megtett össztávolság minimalizálása. A problémának persze online változatát szokták vizsgálni, hiszen egy tűzesetkor nem tudhatjuk, hol üt ki legközelebb tűz, az is lehet, hogy épp azon az állomáson, ahonnan az imént küldtük el a kocsit. Ilyenkor azt nézzük, hogy az optimális költségnek hányszorosát kell fizetnünk legrosszabb esetben (versenyképességi hányados). A sejtés, amelyet általánosan a mai napig nem igazoltak és nem is cáfoltak az, hogy a legjobb algoritmus legrosszabb esetben az optimális költség k-szorosát produkálja. Ez egy sokat vizsgált probléma, sok módosítása is létezik. Az alap probléma pontosabb leírását itt olvashatjuk: http://en.wikipedia.org/wiki/K-server_problem
Mi a kérdésnek olyan verzióját vizsgáltuk, ahol a kérések bizonyos büntetés fejében visszautasíthatóak, minden kéréshez tartozik egy büntetés érték, visszautasítás esetén ez hozzáadódik a költséghez (persze itt is sántít a tűzoltós példa, de bizonyos megrendelések esetén már dönthet úgy a kiszolgáló, hogy ezt neki nem éri meg kiszolgálni akkor sem, ha büntetést fizet). Természetesen itt is van egy megoldatlan sejtés, amit - bár vannak bizonyos eredményeink - általánosságban nyitva hagytunk: ebben az esetben a versenyképességi hányados 2k+1. Challenge accepted!

Miért online algoritmusok?

Először is mik azok az online algoritmusok? Nagyon pongyolán fogalmazva olyan algoritmusok, amelyek nem egyben kapják meg az inputot, hanem részletekben, és a kapott inputrészlettel kapcsolatban azonnali és visszavonhatatlan döntést kell hozni. Általában optimalizálási (minimalizálási vagy maximalizálási) problémáknak vizsgálják online változatát. Általában azt vizsgálják, az online változat célfüggvény értéke mennyivel rosszabb az offline (azaz ahol az input egyben jön) változaténál. Erre vezetik be a versenyképességi hányadost (competitive ratio).
Mire jó ez? A valósághoz közelebbi modellt szerettek volna létrehozni, hiszen a valóságban sem tudjuk sokszor a jövőt, mégis döntenünk kell: pl. egy gyárban gépekre kell kiosztani a munkákat, valamilyen szempont szerint hatékonyan, egy adott munka kiosztásakor (amivel nem várhatunk) nem tudhatjuk, hogy ha valahogy kiosztjuk, nem kapunk-e olyan munkát a jövőben, ami miatt jobb lett volna máshogy kiosztani.
Hogyan lehet ezt kutatni? Nyitott kérdések mindig vannak. Az online algoritmusok területén ez hatványozottan érvényes. Mindig találhatunk olyan optimalizálási problémát, amely online változata még megoldatlan. Ha találtunk egy ilyet, két irányból támadjuk meg:
1. megpróbálunk hatékony online algoritmust konstruálni (ez a könnyebb) és bizonyítani, hogy nem sokkal rosszabb az outputja, mint az optimális (ez a nehezebb), ez adja pl. minimalizálási probléma esetén a felső korlátot,
2. megpróbálunk minden online algoritmushoz konstruálni olyan inputot, amelyre az online algoritmus valamennyivel rosszabb eredményt ad mint az optimális (ezt egy tanárom "kisördög módszer"-nek nevezte), ez adja pl. minimalizálási probléma esetén az alsó korlátot.
Kutatásaimban most leginkább az online algoritmusok elutasításos változatára fogok fókuszálni, amiben az alapprobléma azzal van megspékelve, hogy minden inputrészlethez egy büntetés érték tartozik, az online algoritmusnak lehetősége van elutasítani az adott inputrészletet (mintha nem is jött volna), de ekkor a büntetést ki kell fizetnie. Ennek is van valós alapja: egy megrendelést vissza lehet utasítani, ekkor büntetésként foghatjuk fel a meg nem kapott profitot. Következő bejegyzésben konkrét példákat is láthatunk majd.
--ngyj

Indul a blog

Egy ideje foglalkozom online algoritmusokkal. Hogy miért kezdek blog írásába ezzel kapcsolatban, annak több oka van:
- érdeklődő kutatójelölteknek nyújtanék betekintést a kutatás folyamatába
- megmutatnám, hogy működnek (az online algoritmust vizsgáló) matematikai kutatások azoknak, akik nem tudják elképzelni, hogy is megy ez (mi van ezen kutatnivaló)
- a téma iránt érdeklődőknek kérdéseket vetnék fel
- a témával kapcsolatos kutatásaim (és ennek a blognak vezetése is) az Európai Unió és Magyarország támogatásával, az Európai Szociális Alaptársfinanszírozásával a TÁMOP 4.2.4.A/2-11-1-2012-0001 azonosító számú „Nemzeti Kiválóság Program – Hazai hallgatói, illetve kutatói személyi támogatást biztosító rendszer kidolgozása és működtetése konvergencia program” című kiemelt projekt keretei között valósulnak meg.
A projekt valójában már lassan egy hónapja megy, a bejelentkezés kicsit megkésett, de igyekszem gyakran jelentkezni új bejegyzésekkel.
Szívesen veszek érdeklődő kérdéseket, ötleteket!
--ngyj