Tudományos diákmunka

Elkezdődött a második szemeszter, újabb mérföldkő a hallgatók életében. A diplomamunka készítés újabb fázisa kezdődik. A hallgató, aki az online elutasításos ütemezés kutatásába bekapcsolódott, úgy döntött, hogy ezt a félévet halasztja. Ez nem jelenti a munka szüneteltetését (kutatási munka esetén ez nem is lenne szerencsés), így nyer is egy fél évet, nem kell kapkodni. Másrészt a TDK (Tudományok Diákköri Konferencia) szempontjából sem mindegy, egy hallgató melyik félévben aktív. TDK-n hallgatók mutatják be eredményeiket, amelyeket témavezetőik irányításával értek el. Kér fordulója van, a helyi, és az onnan továbbjutók számára az országos. Mindkettőn három helyezést, valamint különdíjat kaphatnak a legjobbnak ítélt munkák. Egy OTDK első helyezés nyílt utat biztosít a PhD képzésre, természetesen az adott területen. Mint írtam, OTDK (országos TDK) kétévente van, mindig tavaszi félévben. Abban a tanévben, amikor OTDK van, a helyi TDK-t őszi félévben rendezik meg, egyébként a tavasziban. Ezért számít, hogy egy hallgató mikor kezdi a munkát, és utána mely félévekben, meddig aktív a hallgatói státusza. Nem szerencsés tanulmányok végén kezdeni a tudományos munkát, aki utolsó évben kap észbe, szinte biztosan lecsúszik az OTDK-ról, hiszen az eredmények eléréséhez is idő szükséges. Ez mind a hallgató, mind az oktató felelőssége, hiszen az oktatónak kell felfedeznie a jó hallgatókat, a hallgatóknak pedig előrelátóan időben át kell gondolniuk, mit terveznek a jövőjükkel. Hiszen hiába fedezi fel az oktató a jó hallgatót, aki az iparban szeretne elhelyezkedni, ott nem sok plusz értéke van a PhD fokozatnak.
A hallgatóm a fentiek alapján nem jókor kezdett a kutatáson gondolkodni (nekem pedig nem volt esélyem felfedezni őt, mivel a kutatásommal kapcsolatos tárgyat nem tanítottam neki), ezért a mostani OTDK-ról lecsúszott. Eredeti tervei szerint ebben a szemeszterben szeretett volna végezni, de valamilyen okból félévet halasztott, ami járulékos nyereségként új lehetőséget nyitott a TDK-ra. Már "csak" eredmény kell, ami néha akadozva, néha lendületesebben, de alakul. Persze le is kell írni, ez -- főleg elsőre -- nem egyszerű feladat. Hajrá!

Új év, új lendület

Decemberben végül elfogadták a hányatott sorsú cikkünket, így újabb feladatokra koncentrálhattunk. Persze szigorúan csak ünnepek után, hiszen addig kényszerpihenőn voltunk (kötelező szabadság) :)

Több lehetőség adódik. Egyrészt belevágunk a színezés advice complexity vizsgálatába, folytatjuk a megkezdett ütemezős témát, illetve új vizekre is evezhetünk: felmerült automataelméleti téma is, gráfpakolás, illetve a korábban vizsgált gráf-láda pakolás is. Ez utóbbi lényegében már kész, az év végén sokat dolgoztunk rajta, de az utolsó simítások is sok munkát tudnak generálni. Időközben kiderülhet, hogy egy-két dolog nem teljesen korrekt a kéziratban, új ötletek merülhetnek fel, amit még bele szeretnénk írni, illetve az utolsó "Conclusion, further questions" fejezet, és a bevezető is (mindkettőt utolsó lépésként szokás megírni) is okozhat még némi fejtörést. Illetve sok szerző esetén a munka összehangolása is nehezítheti a folyamatot. Természetesen miután a rám eső résszel végeztem, a többi dologra koncentráltam: foglalkoztam az ütemezéssel, elővettem a gráfpakolásos kérdést, amivel szintén már korábban kezdtünk foglalkozni egy munkatársammal, de nagyon szeretnék végre már ezt a megkezdett munkát is befejezni, és az advice complexity kérdésével foglalkozni, ami már izgatja egy ideje a fantáziám. Természetesen lehet párhuzamosan is dolgozni több témán, szoktam is, de azt tapasztalom (nem csak magamon, másokon is), hogy kettőnél (na jó, szélsőséges esetben háromnál) többel egyszerre nem érdemes. Tehát mielőtt újba kezdenék, be szeretném fejezni, aminek a végén járunk. És úgy érzem, a gráfpakolásnak kezdünk a végére érni (a gráf-láda pakolásnak pedig már a végén vagyunk). De már többször csalt meg ez az érzés. Mindenesetre ha nem is újévi fogadalom, de a lendület megvan, hogy az új témát lehetőleg még idén kivesézzem. Alig várom :)

Kellemes ünnepeket!

x = (y + 10) sin (0.2y)

x = (y + 10) sin y

x = – (y+10) sin (0.22y)

Gráf-láda pakolás

Úgy tűnik, kicsit parkoltatjuk még az advice complexity témát. Leporoltunk egy régi, félig befejezett anyagot, hogy tovább dolgozzunk rajta. Ilyen gyakran előfordul: az ember dolgozik valamin, aztán jön valami sürgősebb, vagy egyszerűen nem akaródzik összejönni egy cikkre való, és félreteszi, hátha később előszedve friss szemmel sikerül összehozni. Korábban írtunk egy témaindító cikket a gráf-láda pakolásról Bujtás Csillával, Dósa Györggyel, Imreh Csanáddal és Tuza Zsolttal. Új fogalmat, sőt, új témakört vezettünk be, ami viszont általánosítása sok ismert problémának: ládapakolás (konfliktusokkal és anélkül), gráfpakolás, gráfhomomorfizmus és -izomorfizmus, különböző gráfszínezések, távolság címkézés, csatorna hozzárendelés, partíció, stb.

Az összejött anyagból nem minden került bele a végső cikkbe, a kimaradt anyag pedig nem volt egy teljes cikkre való, és nem is volt egységes. Eljött az ideje, hogy gatyába rázzuk, mivel nem érdemes tovább várni vele, hisze, elfelejtődik, vagy megcsinálja más (a legelső eredmények némelyike nem túl bonyolult), és a kimaradt részek témája is aktuális: online problémák egy formája, valamint egy erősebb modell. Mielőtt az elutasításos változatot definiáljuk, természetesen meg kell vizsgálni az elutasítás nélküli változatot, hogy lássuk, van-e relevanciája egyáltalán az előzőnek. Az erősebb modellben, az ún. jópakolási feladattal kapcsolatban egészen jó eredmények jöttek ki (több gráfosztályra elegendő feltételek, valamint kicsit általánosabban hasonló szerkezetű szükséges valamint elégséges feltételek, amik rögtön fel is vetették a karakterizálhatóság és a bonyolultság kérdését), az online problémának abban a változatában pedig, amelyben az input összefüggő módon kell érkezzen. Ebben a modellben eleve kérdés az online pakolhatóság, ezzel kapcsolatban  az eredeti problémával és a jólpakolás feladattal összehasonlító eredmények jöttek ki, amelyek segítenek elhelyezni a kérdést. És persze egy-két egyszerű állítás különböző feltételekre vonatkozóan, valamint annál több nyitott kérdés. Továbbá az optimalizásálási kérdésekkel kapcsolatban is sikerült megfogalmazni néhány állítást, és persze sok kérdést. A nyitott kérdések, és megfelelő megfogalmazásuk rendkívül fontosak, hiszen ezek tartják mozgásban a kutatást: ha minden érdekes nyitott problémát megoldunk egy adott területen, legfeljebb a nagyon nehezeket nem, akkor annak kutatása előbb-utóbb elhal. Még kerekítjük-gombolyítjuk, hogy csinos cikk váljon belőle, és beküldjük valahová, hátha valóban beindul a téma szélesebb körű vizsgálata. Hajrá, itt sok lehetőség van bizonyítani!

Egy cikk hányatott sorsa

Korábban írtam róla, hogy online hipergráfszínezéssel foglalkozunk. Miután megszületett az eredmény, leírtuk, és beküldtük egy gyors bírálati eljárású laphoz. Sokáig ültek rajta, mire visszakaptuk a bírálatokat. Nem is olyan ritkán előfordul, hogy a bírálatok ellentmondásosak. Persze leginkább akkor történik ez meg, amikor szorít az idő. Nem az történt (amivel már szintén találkoztam), hogy ellentmondó javaslataik lettek volna a módosításra. Jelen esetben az történt, hogy a három bíráló egyike szerint nem érdekes, amit írtunk, más modell (amelyben ahelyett, hogy csak akkor látunk meg egy élet, amikor az utolsó csúcsa is megérkezik, az éleknek a nyomát, azaz trace-ét látjuk minden lépésben) vizsgálatát javasolja, valamint élesebb eredmények kiszámolását a meglévő modellben. A másik két bíráló szerint az eredmények érdekesek, publikálásra érdemesek. Mivel jobb helyeken akkor fogadják el a publikációt, ha minden bíráló egyöntetűen javasolja, lényegesebb változtatások nélkül, itt sem volt másként: javasolták, hogy az előbbi bíráló javaslatai alapján írjuk át a cikket, és küldjük be újra. Mivel szorított a pályázatban vállalt kötelezettségre vonatkozó határidő, még ennél a gyorsnak számító újságnál sem volt remény arra, hogy a revízió és a következő bírálati kör időre lezajlik, és ha még ebben szerencsénk lenne, nem volt semmi garancia, hogy el is fogadják eztán. Ebben az esetben még az sem lett volna elfogadható, ha újabb revízióra küldik a cikket, hiszen akkor kicsúszok a határidőből. Tehát azt a dilemmát, hogy átírjuk-e a kérésnek megfelelően és újra beküldjük, vagy benyújtjuk egy lényegesebben gyengébb újságba, ahol gyorsan elfogadják különösebb kötözködés nélkül, hamar eldöntöttük. Most várjuk a bírálatot, reméljük, hogy jól döntöttünk. Próbálunk kezdeni valamit az először említett bíráló javaslataival. [...] Időközben kiderült, hogy egy részt a bíráló által javasolt "talán érdekes" modellről kiderült egyrészt, hogy nem is egy modell, másrészt az, hogy ezek közül egyik sem ad általánosságban az alapmodellünktől lényegesen eltérő eredményt. Ennek kapcsán felmerült bennünk két kérdés: egyrészt van-e olyan speciális hipergráfosztály, amelyen mégis eltérő eredményt ad (szerintem nem), másrészt mi az advice complexity-je (erről korábban írtam) a problémának (ez több kérdést foglal magába). Gondolkodunk rajta. Talán dolgozunk is rajta. (Folyt. köv.)

Beszámoló a SWORDSról

Kétévente szokták megrendezni a SWORDS konferenciát. A konferencia általában szűk kör számára, jól körülhatárolt témák köré szerveződik, rendszerint helyi szereplőkkel, esetleg máshol kutató munkatársaikkal, társszerzőikkel. A betűszó a Szegedi workshop diszkrét struktúrákról címet takarja.

Az idei kétnapos színvonalas rendezvényen végig ott lehettem. A konferencia fő témája a diszkrét struktúrák. Leginkább algoritmikus problémák kerültek elő. Az előadásokat elsősorban tematikusan szervezték szekcióba, másodsorban kutatási intézmények szerint (pl. a budapesti előadók is egy szekcióba kerültek). Többek között optimalizálási problémák, kombinatorikus játékok, algoritmusok, extremális gráfelméleti kérdések voltak terítéken. Online és szemi-online algoritmusokról több szekció is szólt: transzport problémáról beszélt Dries Goossens, ütemezésről Hans Kellerer, Dósa György és Nysret Musliu, transzport problémáról Dries Goossens, valamint szó volt ládapakolásról is Kim-Manuel Klein valamint Rob van Stee előadásában, továbbá Tuza Zsolt a gráf-láda pakolásról beszélt, amely kidolgozásában az előadó, Bujtás Csilla, Dósda György és Imreh Csanád mellett én is részt vettem.

A konferencia egyrészt lehetőséget nyújtott a találkozásra azokkal a kutatókkal, akikkel van közös terültetünk, esetleg közös cikkünk (Dósa György, Imreh Csanád, Tuza Zsolt), viszont ritkán van lehetőségünk személyesen találkozni. Másrészt jó alkalom volt más neves kutatók megismerésére, akiket legfeljebb futólag ismerek, mert kutatási területük csak marginálisan találkozik az enyémmel, viszont területük elismert képviselői, itt leginkább a Rényi intézetből valamint külföldről érkezett előadókra gondolok.

Volt profitja is a konferenciának: a kutatási területemhez közelebbi előadásokból a friss eredményeket és újabb nyitott kérdéseket, más előadásokból hasznos technikákat, érdekes problémákat ismerhettem meg. Az egyik tág terület, a szemi-online algoritmusok témaköre csak marginálisan kapcsolódik kutatásomhoz, más technikákat igényel, viszont új nézőpontot visz a megközelítések közé, amely tágítja a lehetőségeket, új perspektívákat adva kutatásaimnak.

Újra lendületben

Vége a nyárnak és lement a szeptemberi oktatással kapcsolatos problémák rendezése és adminisztratív feladatok elvégzése (na jó, utóbbi nem igaz, ilyen mindig akad). Lehet végre kutatni! Most annyiban módosul a helyzet, hogy - amint a korábbi posztokból is kiderült - hallgató is bekapcsolódik a munkába. Ennek természetesen előnyei és hátrányai is vannak. Az irodalmazás, terület megismerése részéről lassabban megy, mint rutinos kutatók esetén, ez a folyamat elejét lassíthatja, viszont a helyzetnek a témavezető számára erős motiváló hatása van, hogy időben és kicsit alaposabban körüljárja a témát, átgondolja a lehetőségeket. Egyelőre az elején járunk, ő beleássa magát az irodalomba (választott témája az ütemezés), én keresem az alkalmas témát. Egyelőre Sgall alapcikke, Imreh és Noga Scheduling with machine cost, valamint Bartal et al. Multiprocessor Scheduling with Rejection c. cikke alapján indulunk el. Remélhetőleg hamarosan már előrelépésekről számolok be.