Leírás
A Lineáris 3-Vágás feladatban adott egy digráf 3 kijelölt csúccsal (s,r,t). A cél minimális összsúlyú él- vagy csúcshalmazt találni, ami lefogja az összes s \to r, s \to t, és r \to t utat (az él- és csúcs-súlyozott változat ekvivalens). Könnyen látható, hogy ez legalább olyan nehéz, mint irányítatlan gráfban 3 terminált elválasztani egymástól, tehát NP-teljes. Érdekes módon a Lineáris 3-Vágás approximációs szempontból ekvivalens a következő feladattal: egy irányított gráfban keressünk minimális súlyú él/csúcshalmazt, amit kihagyva nincs sem r-gyökerű feszítő ki-fenyő, sem r-gyökerű feszítő be-fenyő.
Chekuri és Madan bebizonyították, hogy a Unique Games Sejtést feltételezve a Lineáris 3-Vágás feladatot nem lehet jobban közelíteni, mint a természetes LP relaxáció egészértékűségi rése. Az előadáson belátjuk, hogy ez az egészértékűségi rés \sqrt{2}, és meg is adunk egy \sqrt{2}-közelítő algoritmust. Az eredmények Bérczi Kristóffal, Karthekeyan Chandrasekarannal és Vivek Madannal közösek.