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

Timestamp:

06/17/09 10:43:30 (15 years ago)

Author:

Peter Kovacs

Comment:

--

Steiner-hálózat keresése

@@ -1 @@
-== Approximációs algoritmus Steiner-hálózat keresésére ==
+= 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 ===
+== Háttér ==
 
 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.
@@ -13 +13 @@
 
 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 ===
+
+== 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.
@@ -23 +24 @@
 A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
 
-=== Előfeltételek ===
+== Előfeltételek ==
 
  - C++ programozási nyelv ismerete