Changes between Version 3 and Version 4 of Steiner-hálózat keresése

Timestamp:

06/17/09 10:54:33 (15 years ago)

Author:

Peter Kovacs

Comment:

--

Steiner-hálózat keresése

@@ -5 +5 @@
 == 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 [wiki:"Steiner-fa feladat"], amelyre a LEMON már tartalmaz egy [http://lemon.cs.elte.hu/pub/doc/0.7/a00533.html 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.
-
-Formálisan, egy ''G=(V,E)'' gráf bármely két csúcsa között adott egy lokális élösszefüggőségi igény: az ''u'' és ''v'' pontok között ''r(u,v)''. 
-Az ''uv'' él behúzásá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 fog vezetni út.
-
-A probléma NP-teljes már a legegyszerűbb esetekben is. Speciális esete a Lemonban már implementált [http://lemon.cs.elte.hu/pub/doc/latest-svn/a00532.html Steiner-fa approximációs probléma].
 
 == 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, ami 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 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 lineáris programok 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 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 szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.