Hálózat-topológia bővítés lineáris programozással

Több, közelmúltban megjelent cikk rávilágított a hálózatok regionális (azaz egy földrajzi területen fekvő, egymáshoz közeli hálózati elemeket sújtó) hibákkal szembeni sérülékenységére. A dolgozatban definiáljuk a Geometrikus Hálózatbővítés (GH) problémát, adunk egy lineáris programozáson alapuló alsó korlátot a megoldás költségére, majd javasolunk több heurisztikus algoritmust a probléma megoldására. Ezekhez a legújabb számítógépes geometria eszközöket és kombinatorikus optimalizálási módszereket használjuk. A probléma kimenete egy élhalmaz és az egyes élek útvonalai, amiket a hálózathoz hozzákötve robusztusabbá teszik a topológiát. Összehasonlítjuk az algoritmusok teljesítményét és elemezzük a lehetséges megoldásokat. Rámutatunk, hogy a hálózatbővítések - az első intuíciónkkal ellentétben - olcsóak, sőt, az LP-t heurisztika gyakran megtalálja az optimális megoldást.

szerző

• 
  Hajdú Zsombor
  Mérnök informatikus szak, alapképzés
  alapképzés (BA/BSc)

konzulensek

• 
  Dr. Tapolcai János
  egyetemi tanár, Távközlési és Médiainformatikai Tanszék
• 
  Dr. Pašić Alija
  egyetemi adjunktus, Távközlési és Médiainformatikai Tanszék