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!
