SUBSCRIBE tárgyú levéllel lehet.
"Autópálya-dimenzió, legrövidebb utak és bizonyíthatóan hatékony
algoritmusok"
Abraham, Fiat, Goldberg és Werneck cikke.
A két csúcs közötti legrövidebb út meghatározása a gps-es útvonaltervezés kapcsán újra előtérbe került. A kontinensek úthálózata több tízmillió csúcsot tartalmaz, ugyanakkor azt szeretnénk, hogy az optimális útvonalat a másodperc törtrésze alatt megtaláljuk, lehetőleg a gráf méreténél alig nagyobb tárigénnyel. Ehhez a klasszikus Dijkstra algoritmus nem elég.
A közelmúltban számos olyan algoritmus született, amik azon túl, hogy pontosan meghatározzák a legrövidebb utat, a gyakorlatban előforduló úthálózatokra rendkívül gyorsak is. Ezeknek a futásidejét azonban semmilyen nemtriviális gráfosztályra nem sikerült még bizonyítani.
A cikk bevezeti az autópálya-dimenzió fogalmát, és megmutatja néhány korábban ismert algoritmusról (helyenként kicsit módosítva), hogy kis autópálya-dimenzió mellett tényleg gyorsak. A kis autópálya-dimenzió azt jelenti, hogy egy csúcs c*r sugarú környezetében futó, r-nél hosszabb legrövidebb utak kevés csúccsal lefedhetők.
Végül megvizsgálja, hogy a gyakorlatban előforduló úthálózatokra miért jellemző a kis autópálya-dimenzió. Ehhez egy olyan útépítési modellt használ, ami egy alacsony dimenziós euklideszi térben játszódik, ahol a döntések lokálisak és a hosszabb utak sebessége jellemzően nagyobb.
"A Nearly Optimal Algorithm for Approximating Replacement Paths
and k Shortest Simple Paths in General Graphs"
Aaron Bernstein cikke.
Az első feladat az úgynevezett helyettesítő utak keresése, amikor is egy pozitívan élsúlyozott irányított gráfban a legrövidebb s-t út minden élére szeretnénk megkeresni az azt elkerülő legrövidebb s-t utat. Egy kézenfekvő megoldás az, ha a szóbanforgó éleket egyenként kihagyva a gráfból lefuttatunk egy legrövidebb utat adó algoritmust, így O(mn+n^2log n) futásidejű eljárást kapunk. Gotthilf és Lewenstein ezt később O(mn+n^2loglog n)-re javította. Az előadáson egy approximációs algoritmust ismeretetünk, mely az első ilyen típusú megoldás a problémára. Egy [0,1)-beli epsilon értékhez (1+epsilon)-approx algoritmust adunk, melynek futási ideje függ a gráf élein szereplő legnagyobb és legkisebb súly arányától.
A második probléma a következő: keressük meg a k legrövidebb s-t utat a gráfban. Korábban Roditty egy 3/2-es approx algoritmust adott erre a feladatra, a cikk egy (1+epsilon)-approximáló megoldást javasol. Az algoritmus Roditty ötletét általánosítja, ugyanakkor -szemben azzal- a felhasznált módszer az első probléma megoldására is alkalmasnak bizonyult.
"Maximum Flows and Parametric Shortest Paths in Planar Graphs"
Jeff Erickson cikke.
Irányított síkgráfokban a maximális folyam probléma átfogalmazható a gráf duálisára vonatkozó paraméteres legrövidebb út problémává. A legnagyobb olyan paraméter értéke, melyre a duális súlyozása konzervatív, egyenlő a maximális folyam nagyságával. Ez az átfogalmazás egy O(n log n) idejű algoritmust ad a maximális folyam megtalálására síkgráfok esetében. A paraméter növelése közben a legrövidebb utak fenyőjében bekövetkező minden változás O(log n) időben megvalósítható és minden él legfeljebb egyszer kerül be a fenyőbe. Az algoritmus lényegében azonos Borradaile és Klein 2009-es algoritmusával.
A cikkben szereplő példa alapján a módszer nem általánosítható hatékonyan nem síkbarajzolható gráfokra.
"Classified Stable Matching"
Huang cikke.
A cikk a kórház-rezidens problémát terjeszti ki egy másik köntösben. (A kórházak helyett intézményeket, a rezindensek helyett pályázókat veszünk.) Amellett, hogy az intézmények és pályázók rangsorolják a másik oldalt, az intézmények besorolják a pályázókat kutatási területek szerinti osztályokba (ezen osztályok nem feltétlenül diszjunktak). Ezen felül még megadják, hogy minimum és maximum hány főt tudnak felvenni az egyes osztályokba. Célunk olyan (sok-az-egyhez) párosítást találni, amelyben egyik résztvevőnek sem érdemes eltérni az alsó és felső létszámhatárok figyelembevételével. Az előadás első részében megmutatjuk, hogy ha az egy intézményhez tartozó osztályok laminárisak, akkor létezik polinomiális idejű algoritmus; egyébként a stabil párosítás létezésének eldöntése NP-teljes. A második részben felírunk néhány lineáris egyenlőséget azzal a feltétellel, hogy az osztályok laminárisak és nincs alsó korlát az egyes osztályokba felvettek számára. Majd bizonyítjuk, hogy a kapott politop egész értékű. Ezáltal polinomiális időben tudunk találni optimális stabil párosítást ellipszoid algoritmussal.
"Virtuális magánhálózatok"
Apollonio, Grandoni, Oriolo és Sebő cikke.
A probléma alapja: adott egy G gráf (internet), és pontjainak egy részhalmaza (ún. terminálok). Célunk kiépíteni biztonságos csatornákat a terminálok között, minimális költséggel. A cikk egy új, poliéderes megközelítést mutat a megoldásra a római hálózatokon keresztül (adott r, minden út r-be vezet).
"Folyamalgoritmus drótnélküli hálózatokra"
Yazdi és Savari cikke.
A cikk ún. lineáris, determinisztikus kommunikációs hálózatokkal (linear deterministic relay network) foglalkozik. Ez a hagyományos kommunikációs hálózati modellnek egy olyan általánosítása, ahol a csatornában fellépő zajt és interferenciát (determinisztikus) lineáris függvények modellezik. Célunk annak a meghatározása, hogy hány bit információ juttatható el az s forrásból a t nyelőbe. A modellre korábban már bizonyítottak egy min vágás = max folyam jellegű tételt, de a min vágás kapacitású kódolás létezését hosszú blokkokon értelmezett véletlen kódolási séma segítségével bizonyították. A cikkben egy determinisztikus bizonyítás szerepel a tételre, és az optimális kódolási séma kiszámítására polinomiális algoritmust is adnak. A bizonyítások legnagyobbrészt matroidelméletre és szubmoduláris optimalizációra támaszkodnak. Kiderül, hogy a probléma szorosan kapcsolódik a matroid-elméleti Rado-tételhez.