Steiner-hálózat keresése

Lineáris programozást használó 2-approximációs algoritmus implementálása irányítatlan gráfban Steiner-hálózat keresésére.

Háttér

Adott egy irányítatlan G=(V,E) gráf és bármely két csúcsa között egy lokális élösszefüggőségi igény: az u és v pontok között r(u,v). Az uv él használatának költsége c(uv), kapacitása pedig f(uv). Célunk G-nek egy minimális c-költségű H=(V,F) részgráfját megtalálni, amelyben minden uv él legfeljebb f(uv)-szer szerepel, és minden u, v csúcspárra a két pont között létezik r(u,v) éldiszjunkt út. Ez azzal ekvivalens, hogy még ha tetszőleges r(u,v)-1 élet ki is törlünk a gráfból, u és v közt még mindig vezet út.

A probléma NP-teljes már a legegyszerűbb esetekben is. Speciális esete a Steiner-fa feladat?, amelyre a LEMON már tartalmaz egy 2-approximációs algoritmust.

A kérdés gyakorlati alkalmazása, hogy egy meglévő hálózatot (pl. telekommunikációs vagy elektromos ellátó hálózat) szeretnénk minimális költségráfordítással minél biztonságosabbá tenni.

Feladat

A feladat a Kamal Jaintől származó 2-approximációs algoritmus implementálása. Az algoritmus lényege a következő: a probléma természetes LP-relaxáltjának keresünk egy bázismegoldását. Bizonyítható, hogy ebben van olyan él, amely a megoldásban legalább 1/2 értékkel szerepel. Ezt az élt bevesszük a gráfba, újra felírjuk és újra megoldjuk a lineáris programot, és ezt az eljárást iteráljuk.

A probléma megoldása tehát LP feladatok egy sorozatának megoldása. Ez az iterált kerekítések módszerének nevezett eljárás, melyet később számos approximációs algoritmusban alkalmaztak, köztük több is implementálásra érdemes lehet.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.

Előfeltételek

• C++ programozási nyelv ismerete
• gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
• angol nyelvismeret