Eisenberg-Nagy Marianna:
Szemidefinite approximáció és szimmetria redukálás
<br><br>
Számos kombinatorikus feladat NP-nehéz, ezért a problémának csak egy
relaxációját szoktuk megoldani. Mint köztudott, ily módon sokszor
nagyon jó (szoros) közelítést kapunk szemidefinite programozás
segítségével, például a maximális vágás feladatra is.
<br><br>

Feltételek hozzávételével jobb és jobb korlátokat állíthatunk elő.
Különböző meggondolások alapján különböző hierarchiáját definiálhatjuk
így a közelítéseknek. Ám mindegyik ilyen technika hátulütője, hogy a
relaxáció mérete rohamosan nő, ezért gyakran már a hierarchia második
szintjén olyan nagy méretű feladattal állunk szemben, melyet a
jelenlegi megoldók nem tudnak megoldani. Az approximáció méretének
csökkentésére mód nyílik, ha az eredeti feladat nagy mértékű
szimmetriával rendelkezik.
<br><br>

Ám ekkor már nem vehetünk hozzá a közelítéshez tetszőleges feltételt,
mert az megtörheti a szimmetriát, így a méret redukálás lehetőségét
elveszítjük. Megmutatjuk, hogy az Adams és Sherali által bevezetett
RLT technika és a szemidefinit programozási relaxációval kapott
közelítés is megőrzi a szimmetriát a kvadratikus optimalizálási és
kvadratikus hozzárendelési feladat esetén. Ennek segítségével az
ismertnél jobb korlátokat tudunk adni bizonyos nehéz kombinatorikus
feladatokra.