Az iteratív kerekítés technikájaTémavezető: Végh LászlóTéma rövid leírása:Tekintsük a következő feladatot: egy gráfban szeretnénk egy minimális költségű k-szorosan élösszefüggő részgráfot találni. A probléma NP-teljes, és sokáig nyitott volt az a kérdés, hogy lehet-e jó approximációs algoritmust találni. Kamal Jain egy meglepő, új módszer segítségével adott 2-approximációt. Tekinti a probléma lineáris programozási relaxációjának egy bázismegoldását, és erről egy ravasz leszámlálási módszer segítségével bizonyítja, hogy van legalább 1/2 értékű komponense. Ennek értékét felkerekíti 1-re, majd újra megoldja a relaxációt, újra talál egy 1/2 értékű komponenst, stb. A keresett élhalmaz tehát lineáris programozási feladatok egy sorozatának megoldásából adódik.Ez az iteratív kerekítések módszerének első megjelenése, ami aztán több, látszólag különböző területen került elő, és segítette elő nehéz approximációs kérdések megoldását. A szakdolgozat célja a technika megismerése és mélyebb megértése. |