Véletlen

Szerencsére az nem véletlen, hogy újra jelentkezett a hallgató, aki most kezdi a diplomamunkáját. A véletlenített online algorimusok témakörét szemelte ki, és szimpatizál a ládapakolással (bin-packing). Ez ígéretes, kellőképpen leszűkítette a témát, de bőven hagyott lehetőséget, hogy a dolgozat célja szándékai szerint alakulhasson. Mivel szorgalmas és időben vagyunk, nem szeretnék beleszólni. Véleményem szerint egy jó témavezető nem a saját elképzelését erőlteti a hallgatóra, hanem elmondja a lehetőségeket (a számára nem szimpatikusakat is), és hagyja, hogy a dolgozat készítője alakítsa. Közben fejlődik, képezi magát, hogy a lehető legtöbb segítséget meg tudja adni (bin-packing témakörben nem vagyok a legjártasabb, ideje még többet olvasnom róla :) ). A ládapakolás nagy témakör, és ha valaki nem jártas benne, könnyen elveszhet a sok irodalom között. A téma szűkítése segít, de ilyenkor nem szégyen, és hasznos, ha olyan kutatóhoz fordulunk tanácsért, aki ezzel foglalkozik.

Újabb diplomamunka

Elkezdődött a tanév, és nagy örömömre újabb MSc hallgató érdeklődött az online algoritmusok témaköre iránt. Mivel nem határozott témajavaslattal kopogott be, végigjárjuk a témakeresés és a cél megfogalmazásának útját. Hosszadalmas, de megéri. Először egy általános leírás (újra csak Dósa György és Imreh Csanád tananyaga) a kiindulópont, szűkítjük a témát, ahhoz keresünk célirányos irodalmat, közben megfogalmazzuk a dolgozat célját. Ezek a következők szoktak lenni (de egy szokatlan javaslatnak is örülnék):

• adott témában a lényegesebb eredményeket összefoglaló munka (survay)

•  egy konkrét (angol) nyelvű cikk fordítása és magyarázata, pl. a nem részletezett, pontatlan bizonyítások kirészletezésével, példákkal

•  speciálisabb téma esetén önálló munka, pl. egy matematikai eszköz önálló alkalmazása problémákra (akár már megoldott problémák új megoldása), vagy egy probléma általánosítása, esetleg épp speciális esetek vizsgálata (amiket nem részleteznek ki cikkekben, de nem feltétlen új eredmények)

• új, önálló eredmény, ebből TDK is születhet, de ha nem sikerül, pl. nem jön ki ismertnél jobb eredmény, diplomamunkának az még akkor is jó

• elméleti eredmények gyakorlati alkalmazása (ez általában akkor merül fel, ha céggel van kapcsolatban a dolgozat írója, és konkrét problémára keresnek megoldást, pl. egy gyárban a gépek beállítása bizonyos feladatokhoz, anyag szabása optimálisan, stb.), persze ilyet hipotetikusan is lehet vizsgálni, de nagyon meg kell magyarázni a motivációt

• oktatási célú tananyag készítése (nem survay, de ha a hallgató nem tanárszakos, a középiskolás szintnél tovább kell mutasson, szemléltetéssel, emellett tanításra alkalmas anyagnak kell lennie).

 Persze ez nem rögtön körvonalazódik, jó esetben is hónapok telhetnek el, mire kialakul egy konkrét elképzelés, miről és hogyan fog szólni a dolgozat.

Újabb cikk

Újabb cikkünket fogadták el (Iván Szabolccsal közöset: On nonpermutational transformation semigroups with an application to syntactic complexity), a megjelenésre egyelőre még várunk (valószínűleg hónapokat, remélhetőleg nem éveket...) Ez kicsit más témájú. A tudományterületeket megpróbálják körülhatárolni, de a kutatások sokszor átlépnek határokat, ún. interdiszciplináris témává válnak. Az algoritmusok témakörét sem lehet élesen elválasztani más területektől: szoros kapcsolatban van az automaták elméletével, az algebrával, a bonyolultságelmélettel, a kombinatorikával, a geometriával... Minél több területtel van kapcsolata, annál gazdagabb az eszköztára egy témának. Persze már volt róla szó, hogy előre sosem tudhatjuk, hogy egy eszköz hasznos lesz-e számunkra. Az online algoritmusokat természetesen az algoritmuselmélet részterületének tekinthetjük, de nagyon szoros kapcsolatban van a kombinatorikával, és a bonyolultságelmélettel (complexity theory). Ezért óvatosan, de érdemes néha más területekre evezni.

Globposzt

Ezen a vidám április elejei napon egy érdekes alkalmazásról írok. A Globulation nevű real-time (valós idejű) stratégiai alkalmazás valóságközelibb, mint a turn-based alkalmazások. Van offline, valamint  hálózatban futó változata. Több algoritmus van mögötte, különböző módokon próbálnak optimalizálni. Kétféle egység kaphat utasításokat, amelyeket az alkalmazás automatikusan oszt ki az egyes egységeknek, az egyik a worker, a másik a warrior, nevük is jelzi funkcióbeli különbségüket. Amennyiben az adott egység sérült vagy erőforráshiány lép fel, a feladatot visszautasíthatja. A cél  a presztízspontok mennyisége valamint az elfoglalt terület maximalizálása. A célfüggvény összetettsége miatt több optimális stratégia létezik, ez okozza a feladat nehézségét. A versenyképességi hányadosra éles korlát nem ismert a számítás komplexitása miatt, bár valójában kevesen foglalkoztak még a kérdéssel. Legtöbb esetben nem optimalizálni próbálnak, hanem egy adott célfüggvényértéket elérni, ennek elérése esetén nem növelik tovább a célfüggvényt, ilyen megközelítésben a versenyképességi hányadost számolni nincs értelme. Más célfüggvény vizsgálata merülhet fel ilyenkor, például az adott terület/pontérték eléréséhez szükséges idő, természetesen ennek a minimalizálása a cél. Sem éles versenyképességi korlátok, sem approximációs algoritmusok nem ismertek erre a kérdésre sem.

Megjelenik egy újabb cikk -- vééégre

A napokban kaptam értesítést arról, hogy megjelenik egy cikkünk. Hirtelen nem is tudtam, melyik cikkről szólnak. Aztán összeállt a kép. Ugyanis egy régen (még jóval a jelen projekt kezdete előtt fogadták el, és online nem sokkal a projekt kezdete előtt meg is jelent) elfogadott cikk papír változatáról szólt az értesítés. Volt már róla szó, hogy a matematikai témájú cikkek publikálási folyamata lassú, nem ritkán évekig eltarthat, elsősorban a bírálati folyamat nehézkessége miatt. Matematikában az eredmények helyességét ellenőrizni nehezebb, mint például egy pszichológiai témájú írás esetén. Itt azonban nem arról van szó: már elfogadott, online változatban megjelent cikk újságváltozatáról, évfolyammal, számmal, oldalszámmal. Rangosabb folyóiratoknál előfordul, hogy sok színvonalas írást küldenek be, egy számban korlátozott a benne megjelenő cikkek száma, így várólista alakul ki az elfogadott cikkekből, amelyek várják a sorukat, hogy bekerüljenek valamelyik számba. Ezért vezették be az online megjelentetést, hogy más kutatók addig is láthassák és hivatkozhassák (hiszen az impakt faktorba is csak a két éven belüli hivatkozások számítanak bele, a hivatkozás pedig az újság érdeke). Az online megjelenés is megjelenésnek számít, tehát nem változtatható, vagyis utólag nem íratható bele még támogatás szövege sem, hiába jelenik meg az újságváltozat egy adott projekt ideje alatt. Viszont az online megjelenés sok helyütt nem számít publikációnak, így kerül két szék között a földre egy kutató ilyen helyzetben, hiszen előfordulhat, hogy emiatt sehová sem tudja elszámolni a publikációját. Így jártam.

Visszatérve a hamarosan megjelenő cikkre: csak hogy nevet adjak a gyereknek, a

L. Epstein, Cs. Imreh, A. Levin, J. Nagy-György, Online File Caching with Rejection Penalties, ALGORITHMICA 71:279–306, 2015 

munkáról van szó. Ebben a publikációban a lapozási (paging) probléma kicsit más irányú általánosításáról van szó, mint a k-szerver probléma, de rokon vele valamilyen értelemben. A file caching problémában az input fájlokból álló kérések sorozata egy lassú memóriából. A fájlnak két attribútuma van, egy pozitív kinyerési költség és egy egész méret. Egy algoritmusnak egy k méretű cache-t kell fenntartani, úgy, hogy a cache-ben tárol fájlok teljes mérete sosem haladhatja meg k-t. Adott egy kérés egy fájlra, amely nincs jelen a cache-ben a kérés időpontjában, ekkor a fájlt a lassú memóriából a cache-be kell vinni, valószínűleg más fájlok elmozgatásával onnan. Ez a kért fájl kinyerési költségével jár. A lapozási problémán kívül (ahol minden költség és méret 1) a probléma jól ismert speciális esete a költség modell vagy más néven a súlyozott (weighted) lapozás, ahol minden méret 1, a hiba (fault) modell, ahol minden költség 1, és a bit modell, ahol minden fájl mérete és kinyerési költsége megegyezik. Ha figyelmen kívül hagyás (bypassing) megengedett, akkor a fájl hiány még mindig a fájl elérését eredményezi a lassú memóriából, de annak későbbi cache-be beszúrása optimális. Mi a fenti problémák online elutasításos változatát vizsgáltuk, amelyben minden egyes kéréshez büntetés is tartozik. Ekkor ha a cache-ben jelen nem lévő fájl kérését elutasítja az algoritmus, akkor a költségéhez a kérés büntetése járul hozzá. A célfüggvény az elutasított kérések büntetésének és az elfogadott kérések kinyerési költségének összege. Ez a probléma mind a caching, mind a caching with bypassing probléma általánosítása. Determinisztikus és véletlen algoritmusokat is kidolgoztunk. A véletlen algoritmus versenyképességi hányadosa O(log k), és ez konstans faktortól eltekintve optimális. A determinisztikus esetben ismert  k-versenyképes algoritmus a cachingre és (k+1)-versenyképes algoritmus a caching with bypassig problémára.Továbbá ezek a legjobb ismert versenyképességi hányadosok. Ezzel ellentétben megmutattunk egy 2k+1-es alsó korlátot az elutasításos változat determinisztikus algoritmusainak versenyképességi hányadosára, amely még a lapozásra is érvényes. Kidolgoztunk egy (2k+2)-versenyképes algoritmust az elutasításos caching problémára, valamint egy (2k+1)-versenyképes algoritmust, amely alkalmazható az elutasításos lapozásra, valamint a caching hiba és bit modelljeiben.

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.

Hogyan írjunk szakdolgozatot/diplomamunkát?

Ebben a posztban szeretnék segítséget nyújtani azoknak, akik szakdolgozatot vagy diplomamunkát szeretnének írni online algoritmusok témakörében, de igyekszem gyakorlati tanácsokat adni minden leendő szakdolgozatírónak is. Dolgozatot írni sokféleképpen lehet. Itt egy megközelítést mutatok, de nem állítom, hogy ez az egyetlen üdvözítő módszer. Szedjük pontokba a folyamat fázisait.

1. Irodalmazás. Ezt szinte sosem ússzuk meg, hiszen a munkának valami újat kell tartalmaznia, nem csak a tanultak összefoglalását vagy közvetlen alkalmazását. Algoritmusokhoz általában hasznos könyveket szerkesztett Iványi Antal Informatikai algoritmusok címmel (I. és II. is elérhető online), online algoritmusokhoz a második köteten felül Dósa György és Imreh Csanád Online algoritmusok elektronikus jegyzete hasznos kiindulási alap. Ha sikerül szimpatikus témát választani, akkor annak megfelelő szakirodalmat lehet tovább keresni, ezt általában már angol nyelvű szakcikkek formájában. Hasznos tanács lehet, - saját hibámból okulva írom - hogy ha az irodalomban látok valamit, amit fel szeretnék használni, akkor ne csak az adott dolgot jegyzeteljem ki, hanem hogy pontosan hol találtam, nem csak a visszakereshetőség miatt, hanem azért is, mert a dolgozat formai követelményei között szerepel, hogy a hivatkozások korrektek legyenek.
2. Munkaterv. Ez nem szükséges része a dolgozatnak, inkább ez is tanács, bár a saját diplomamunkázóimtól el szoktam várni az elkészítését az első féléves kurzus teljesítéséhez. Ha körvonalazódik a téma és kialakul az elképzelés a dolgozat jellegét illetően, akkor érdemes egy tervet készíteni, például egy vázlat formájában, ami akár a dolgozat tartalomjegyzéke is lehet majd, hogy keretet adjunk a munkának, ne legyen terjedelmes, ne folyjon szét, ne számoljunk/írjunk csak úgy a vakvilágba. Ha van egy viszonylag pontos elképzelésünk, ami a tervben manifesztálódik, akkor kisebb eséllyel futunk felesleges köröket, és csökkenthetjük a redundanciát is munkánkban.
3. Dolgozatírás előtti munka a dolgozat jellegétől függő lehet: ha összefoglaló munkát írunk, akkor irodalmazás után, esetleg már közben rögtön megkezdődik a munka formába öntése, míg ha számolunk (vagy géppel számoltatunk) valamit, akkor nem feltétlenül hasznos, ha rögtön elkezdjük leírni. Mindig az adott munka tükrében mérlegeljük, mikor érdemes belefogni dolgozat írásának. Hasznos tanács lehet, hogy ne fogjunk az írásba túl korán, amíg csak részeredményeink vannak, mert előfordulhat, hogy sokszor átírjuk/átszerkesztjük a dolgozatot, felesleges pluszmunkát generálva magunknak (és a témavezetőnek). Persze túl későn se, mert lemaradunk a beadási határidőről... 
4. A dolgozat írása. Újra egy elkerülhetetlen fázishoz értünk. Ha követtük a fenti menetrendet, akkor a munkaterv adta vázlatot kell tartalommal kitölteni a munkánk eredménye alapján. Matematikai dolgozatot LaTeX-ben célszerű írni, magyar nyelvű rövid segédanyag is elérhető hozzá.
   Hasznos tanácsok:
   - A dolgozat legyen jól tagolt, áttekinthető, ne folyjon össze a sok szöveg. Ez elérhető megfelelő fejezetekre és bekezdésekre való bontásokkal, felsorolások, táblázatok és ábrák beszúrásával (ezek megfelelő használata igen mutatóssá teheti a dolgozatot), nagyobb/fontosabb képletek kiemelésével. Vigyázat: nagyobb táblázatok/ábrák mellékletbe teendők a szövegbe ágyazás helyett!
   - Ábrák készítéséhez célszerű tikz csomagot vagy olyan programot használni (xfig, gnuplot), amelyek támogatnak LaTeX módot, mert az ilyen módon beillesztett képekben lévő szöveg mérete, karaktertípusa nem fog eltérni a sima szövegétől.
   - Érdemes követni a szokásos bevezetés-tárgyalás-befejezés felépítést. A megfelelő arányok eltalálása első dolgozat írásánál nem könnyű, a témavezető segítségét lehet kérni. Tipikus hiba a túl hosszú felvezetés, korábbi eredmények, felvezetés túl hosszú tárgyalása a lényegi témához képest. Másik tipikus hiba (természetesen nem az előzővel azonos dolgozatban) a túl rövid bevezetés, a téma ismertetésének, fogalmak definiálásának túl rövid volta vagy hiánya. Nézegessünk (de ne másoljunk) hasonló témájú szakdolgozatokat, diplomamunkákat, lehetőleg jeles minősítésűeket!
   - Kerüljük a személyes vonatkozású mozzanatokat, mint pl. a kutatással kapcsolatos nehézségeinkre való panaszkodást, és a nagyobb kitérőket is (pl. csak lazán kapcsolódó eredmények ismertetése, aminek a fő témához kevés köze van). Azért persze nem kell szürke és száraz dolgozatot írni, hosszabb magyarázat, szemléltetés, sőt, még egy kis humor is belefér ;)
   - A dolgozatból derüljön ki, melyek a saját eredményeink, és melyek másoké. A fentebb említett hivatkozások a szakirodalomban látható módon legyenek megadva, példaként a tézisfüzetem és az egyik diplomamunkám hozom fel.
5. Nyomtatás, köttetés. Gyakran késésben történik, és valamit Murphy is alkot közben. Ne idegeskedjünk! ;)

További tanácsok itt találhatók.

Írassunk diplomamunkát!

A kutatói munkának fontos része az utánpótlás biztosítása. Ez a szakdolgozattal/diplomamunkával/TDK-val kezdődik, PhD-vel folytatódik, és szerencsés esetben még a nyugdíjjal sem ér véget. Abban a szerencsés helyzetben vagyok, hogy újra együtt dolgozhatok egy hallgatóval a diplomamunkáján. Ez kezdetben nekem több munkát jelent, később pedig egyre inkább a hallgató önálló munkája veszi át a hatalmat, én pedig jó esetben nézhetem ölbe tett kézzel, ahogy a munka alakul :) Ez persze nem teljesen így van, főleg egy TDK/PhD esetén, a témavezetőnek mindig van feladata, terelgetni a munkát a megfelelő irányba, de egy kisebb dolgozatra igaz lehet.
Mi jelenti itt a témavezető felelősségét és feladatát? A felelősség ott van, hogy a tapasztalatát felhasználva olyan témát adjon, ami az adott szinten teljesíthető, viszont kihívást is jelent és megfelelő képesség és befektetett energia esetén színvonalas eredmény születhet. Tudni kell, milyen téma alkalmas szakdolgozati témának, milyen téma PhD-nek. Ehhez össze kell gyűjteni az adott témához kapcsolódó alapvető irodalmat úgy, hogy az alapján megfelelő képet kaphasson a témavezetettje a területről, de ne árassza el feleslegesen sok olvasmánnyal. Meg kell találni a megfelelő témavezető/hallgató munka arányt, meg kell ismerni a hallgatót annyira, hogy lássa, mennyi segítségre, iránymutatásra van szüksége, mennyire képes önálló munkára, és úgy irányítani a folyamatot, hogy azért a munka nagy részét mégse a témavezető végezze el. Minél több gondolkodást igénylő feladatot tűzünk ki, ez annál nehezebb... Persze könnyebb a helyzet, ha korábbi munka folytatódik, azaz a hallgató, aki a diplomamunkáját készül írni, korábban az adott témában az adott témavezetőnél írt szakdolgozatot, vagy TDK-zott, aki a PhD tanulmányait kezdni, hiszen az ismerkedésen túl vannak a felek, és nem akkor kezdik nézegetni a témát sem. Mi most találkoztunk először (leszámítva egy kurzust, ahol tanítottam), és még az irodalmazás fázisában tartunk, vagyis még ott sem, ki kellene választani a témát, ami tetszik, hogy irodalmat adhassak, mert nem szeretnék túl sokat adni elsőre. Így nem is tudom még, mi lesz a konkrét téma, közben alakul majd, illetve ebben a fázisban azt sem tudom, mennyi témavezetői támogatásra lesz majd szüksége a hallgatónak.
Később, amikor a konkrét munka elkezdődik, akkor eleinte jobban irányítani kell, esetleg ötleteket adni a számoláshoz, gyakran ellenőrizve azt, később az ellenőrzés kerül majd túlsúlyba a feladataim közül szerencsés esetben. Ha sikerül érdekes eredményt kihozni, - ami szintén a témavezető felelőssége, - akkor TDK dolgozat, ha nem megfelelő félévben vagyunk*, akkor esetleg cikk születik belőle (előbbi esetben sincs kizárva ennek lehetősége, sőt), ami megalapozhatja a későbbi PhD-t. Munkára fel!

* OTDK 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. Ha végzős hallgató kezd el dolgozni valamin olyan évben, amikor OTDK van, akkor nincs esélye még helyi fordulóra sem. Ez az év ilyen, és mi is így jártunk...

(Szerző)társasan szép az élet

Dolgozunk. Többször használtam többes számot, és ez esetemben nem királyi. Könnyebben tudok dolgozni másokkal. Persze nem mindegy, kivel, az összehangolt munkához meg kell találni a számunkra megfelelő partner(eke)t. Nem mindenkire, de sokakra igaz ez: egyedül nehezebben megy. Ismerek olyat is, aki egyedül is rendkívül termékeny kutatási szempontból, de ő kisebbségben van az ismerőseim között e tekintetben.
Tehát gyorsabban megy a munka, ha megosztjuk. Általában. Most éppen hátráltat, hogy nem egyedül csinálom (bár csinálhatnám, semmi nem tart vissza, próbálkozok is), mivel időnként nem árt megkonzultálni a tények állását, és így nyáron, főleg klímaszünetben ezt nehézkes összehozni. De általában erősen motivál, hogy én is hozzátegyek, haladjak, mit szól a másik, ne mondjam már neki, hogy ötletem sincs, megakadtam.

Hogy kezdődik ez? PhD hallgatóknál általában a témavezetővel, ideálisabb esetben a témavezető más témavezetettjeivel is kezdünk együtt dolgozni (azért ideálisabb, mert szimmetrikusabb a viszony velük). Aztán megismerkedünk a témavezetőnk más társszerzőivel, szerencsés esetben velük is elkezdünk dolgozni, konferenciákra járunk, ott ismerkedünk, és számos más lehetőség is megnyílik idővel. Matematikában ideálisan 2-4 (esetleg 5) ember szokott tudni jól együtt dolgozni, egyedül sokaknak lassan megy, több ember munkáját pedig nehézkesebb összehangolni (már 2 esetén sem egyszerű, a kutatók számának növelésével egyre nehezedik, itt nem kísérleteket végzünk, ahol ki lehet osztani a jól körülírt részfeladatokat, bár ilyesmi is előfordulhat, ha esetekre bontható az adott kutatás kérdése). Időnként előfordul, hogy több szerzős cikk jelenik meg, ilyet pl. extrém esetben egy konferencián összejött társaság dobja össze és egyikük leírja, de találkoztam olyannal is, hogy közel ugyanabban az időben több szerzőtársaság hozta ki ugyanazt az eredményt, és végül közösen írták le.

De én most itthon ülök és a újabb problémával próbálok foglalkozni, de nem motivál, hogy a szerzőtársamat nehezen érem el. a szakirodalmat már elkezdtük együtt átnézni, már a problémát is kitűztük. Máskor volt olyan is, hogy villámgyorsan, napok alatt volt eredmény, amikor intenzíven dolgoztunk (más munkatársammal pedig évekig elbeszélünk egymás mellett, mert valahogy nem sikerült megtalálni a közös nyelvet, csak mostanában kezdem végre érteni, miről beszél). Megosztottuk a feladatokat, egymás eredményeit vittük előre vagy éppen cáfoltuk meg, mindenki azt a részt vállalta, amiben jó, ez nagyon gördülékenyen tud menni egy összekovácsolódott csapatban. Persze nem nyáron. Most hetekig nincs alkalmunk találkozni, így van időm töprengeni a feladaton. El-elmerengek rajta időnként, de kicsúszik a kezeim közül, mint egy nyálkás hal, pedig érdekes, nem túl nehéznek tűnő probléma. Amiből esetleg még PhD-téma is születhet. Csak meg kéne szülni valakinek...

Kikacsintás

Eddig, mint a második posztban írtam, leginkább az online problémák elutasításos változatával foglalkoztam. Most felkeltette az érdeklődésemet az ún. advice complexity (nem ismerek rá magyar kifejezést). A fogalom a bonyolultságelméletből jön, az érdekli a kutatókat, hogy adott bonyolultsági osztályba mely problémák esnek ha kaphatnak plusz biteket, és mennyit az input hosszának függvényében (akinek ez zavaros, nézze meg a linket). Az online algoritmusokba is beemelhetjük a advice string fogalmát és megfogalmazhatunk olyan kérdéseket, hogy mennyi advice bit szükséges, hogy az online algoritmus elérje az optimális költséget, vagy adott c-re c-versenyképességet érjünk el. Approximációs sémákat is megfogalmaznak: tetszőleges ε esetén 1+ε versenyképességre törekednek minél kevesebb advice bit felhasználásával.
A modell önmagában is érdekes, bár sok kérdést már megoldottak benne (k-szerverre, ládapakolásra, ütemezésre, gráfszínezésre, stb., bár még bőven hagytak nyitva is), de ha kombináljuk meglévőekkel (pl. az elutasításos modellel), akkor lehetőségek széles skálájával találjuk szembe magunkat. Még mi sem tudjuk, hol kezdjük, ez a bőség zavara :)

Beszámoló a CSM-ről

A konferencia címe CSM - The Third Conference of PhD Students in Mathematics. Nem kell hozzá sokat tudni angolul, hogy rájöjjünk, elsősorban PhD hallgató voltak ott (meg hallgatók, meg fiatal kutatók).
A konferencia fő célja, hogy a fiatal kutatópalánták első szárnypróbálgatásának helyszíne legyen, hasonlóan izguló és tapasztalatlan társaik előtt mondják el először eredményeiket, ne a szakma legjelesebb képviselőinek. Másrészt célja az egymással és egymás témájával való ismerkedés, azaz szakmai kapcsolatteremtés is. Ezt segíti, hogy némiképp témák köré szerveztük a szekciókat (általában így szokták, szervezéskor mi is odafigyeltünk erre), így közel egy időben beszéltek a hasonló témával foglalkozók, lehetőségük volt egymástól kérdezni, észrevételeket, javaslatokat tenni. Persze hasznos távolabbi területek képviselőivel is kapcsolatot tartani (éppen a napokban segítettem ki kombinatorikai bizonyítással egy differenciálegyenletekkel foglalkozó kollégámat), erre is megfelelő terep ez a konferencia.

A rendezvényen a differenciálegyenletek témája túlsúlyban volt, köszönhetően a nálunk ezzel a témakörrel nagy számban foglalkozó PhD hallgatónak és fiatal kutatónak. Volt ezen felül két-két szekciónyi algebra és geometria témájú előadás, egy sztochasztika és egy kombinatorika szekció. Bár némelyeknél érezhető volt az izgalom, a konferencia jellegéhez képest meglepően színvonalas előadásokat lehetett hallani -- bár tény, sokuknak valójában ez már nem az első konferencia előadása volt. Mivel sok előadás volt, ezeket nem részletezem, a konferencia honlapján megtalálhatóak az absztraktok, az előadások nem tartogattak ezekhez képest nagy meglepetéseket.

Az utolsó nap vége felé én is előadtam a legfrissebb eredményünket. Korábbi posztban írtam róla, hogyan készültem az előadásra, és valamennyit magáról a konferenciáról is. Az előadások 25 percesek voltak (kivéve a meghívott előadókét, akik 50-50 percet beszéltek), plusz 5 percet hagynak az előadás utáni kérdéseknek. Ezt kicsit hosszúnak tartottam, és nem voltam ezzel egyedül. Mivel nem a szűk szakterület képviselőinek beszéltem, részletesebb bevezetőre volt szükség, hogy értsék, miről beszélek, és így már nem is jutott olyan sok idő a tényleges eredményekre. Ezek felsorolásán felül azért még belefért egy rövid bizonyítás és egy ábrán szemléltetett bizonyítás vázlat.

A másik oldalba -- mint céloztam rá, a szervezők között voltam én is -- érdekes volt belelátni. Bár a sok kommunikációt igénylő feladatokat (meghívások, jelentkezések fogadása, résztvevőkkel kommunikálás, szállás, vacsora szervezése, szponzorok megkeresése, helyszín szervezése) nem láttam el, inkább szerkesztési munkákat (weblap, program, stb.), azért ezekre némi rálátásom nyílt, láttam, mennyi részletre kell figyelni, mik okozhatnak problémát, ezeket hogyan lehet orvosolni, illetve legközelebb kiküszöbölni. 

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.