SUBSCRIBE tárgyú levéllel lehet. Érdemes
feliratkozni, minden alkalom előtt szétküldjük az absztaktot!
"Hatékony heurisztikák legnagyobb közös részgráfok keresésére"
Englert Péter és Kovács Péter cikke.
Gráfok legnagyobb közös részgráfjának meghatározása egy NP-nehéz optimalizálási probléma. Számos alkalmazása van, többek között a kémiai informatika területén, ahol molekulagráfok legnagyobb közös részstruktúráit keressük. Az előadáson megmutatjuk, hogy a probléma két változata hogyan vezethető vissza a maximális klikk feladatra. Ezt a transzformációt felhasználva adunk egy hatékony heurisztikus algoritmust, valamint bemutatunk különböző heurisztikákat, amelyek nagy mértékben javítják az algoritmus pontosságát. Ezen kívül olyan módszereket is tárgyalunk, amelyek a kémiai alkalmazásokban felmerülő speciális követelményekre, általánosításokra nyújtanak megoldást.
Az előadás után cikkosztás volt.
"Közel stabil iskola-optimális felvételi mechanizmus a diákok részéről
közelítő taktikázásbiztossággal"
Kanna, Morgenstern, Roth és Wu cikke.
Az iskola-optimális stabil felvételi sajnos nem taktikázásbiztos, a diákoknak megéri hazudni a preferenciáikról. Korábbi cikkekben olyan eredmények szerepeltek, hogy bizonyos feltevéseket téve (pl minden diák konstans sok iskolába jelentkezik, és iskoláit egyenletes véletlen szerint választja) lehet olyan mechanizmust adni, ami iskola-optimális és a diákok 1-o(1) részének domináns stratégiája az igazmondás. A bemutatott cikk más utat választ: Nem tesznek fel semmit a preferenciákról, hanem a stabilitás-fogalmat enyhén lazítva a differential privacy koncepcióját alkalmazva olyan mechanizmust adnak, ahol minden diáknak várhatóan csak kevés haszna származhat a hazugságból, és a kapott felvételi közelítően stabil és iskola-optimális (meghatározott értelemben).
"2-élösszefüggőség digráfokban"
Georgiadis, Italiano, Laura és Parotsidia cikke.
A 2-élösszefüggő blokkok meghatározása lineáris időben jól
ismert irányítatlan gráfokban, viszont ezt (az egyébként elég természetes)
kérdést nem igazán vizsgálták eddig digráfokban; míg O(nm) idejű algoritmus
egyszerűen adható, ennél jobb nem volt ismert. A feladatban a fő nehézség
az, hogy, az irányítatlan esettel ellentétben, digráfokban a 2-élösszefüggő
blokkok nem egyeznek meg a 2-élösszefüggő komponensekkel.
Az előadásban megoldjuk a fenti feladatot.
"Elosztott számítások nagyméretű gráfproblémákra"
Klauck, Nanongkai, Pandurangan és Robinson cikke.
A k-gépes modellben k darab páronként összekapcsolt gépen futtatunk egy elosztott algoritmust. A kommunikáció szinkronizált, és a gépek minden körben páronként legfeljebb W bitet küldhetnek át egymásnak. A szerzők számos alapvető gráfprobléma bonyolultságára adnak alsó és felső korlátokat (a körök számát tekintve) ebben a modellben.
Feltesszük, hogy az n csúcsú input gráf csúcsai (együtt az illeszkedő élekkel) egyenletesen véletlenül vannak szétosztva a k gépen, illetve megengedjük, hogy az algoritmusok epszilon valószínűséggel hibás eredményt adjanak. Az alsó korlátokhoz információelméleti eszközökkel \Omega(n/k) korlátot adnak egy feszítőfa meghatározásához szükséges körök számára, illetve kommunikációs bonyolultságot használva \Omega(n/k^2) korlátot adnak az összefüggőség és a feszítőfa tulajdonság ellenőrzésére. (Ezzel számos más feladat bonyolultságára is alsó korlátot mutatva.)
A felső korlátokhoz egy másik, sokat vizsgált számítási modell, a CONGEST modell eredményeit alakítják át a k-gépes modellre, felső korlátot adva így többek között a minimális súlyú feszítőfa, összefüggőség és feszítőfa tulajdonság ellenőrzés, részgráf izomorfia, legsűrűbb részgráf, legrövidebb utak és PageRank feladatokra.
"Approximációk az oszthatatlan folyam problémára útgráfokon"
Batra, Garg, Kumar, Momke és Wiese ill.
Anagnostopoulos, Grandoni, Leonardi és Wiese cikke.
Az UFP problémában adott egy út, az élein pozitív egész kapacitásokkal, illetve néhány feladat, minden feladathoz egy részút, egy pozitív egész igény (folyam érték) és egy nemnegatív profit. A cél, hogy kiválasszuk a feladatok egy részhalmazát, amelyekre minden élen a folyamérték a kapacitás alatt van, és a profit maximális. A problémára adunk egy kvázi-PTAS algoritmust, és két speciális esetben pedig PTAS algoritmust: ha minden feladatra az igény és a profit arány egy rögzített intervallumba esik, illetve ha a részutak hosszát (1-delta)-szorosra rövidíthetjük. A maradék időben vázolni fogom Anagnostopoulos et al. 2+eps-approximációs algoritmusát az általános problémára.
"Homomorfizmusok eloszlása"
Egy F és G gráf esetén jelölje Hom(F,G) az F csúcsait a G csúcsaira képező homomorfizmusok (éltartó leképezések) halmazát. Szegedy Balázs homomorfizmusok entrópiájával és a logaritmikus gráflimesszel kapcsolatos eredményei motiválják, hogy homomorfizmusok éleken való eloszlásait vizsgáljuk. Azt szeretnénk megérteni, hogy egy ritka gráfban melyek azok az élek, amelyek törlése a homomorfizmusok számát drasztikusan megváltoztatják. Az előadásban az ezzel kapcsolatos kérdéskörről fogok beszélni.