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