Bérczi Kristóf: Maximális közös független halmazok approximációja matroidokban (Linhares, Olver, Swamy és Zenklusen cikke)

Edmonds tétele karakterizálja két matroid maximális közös
független halmazának a méretét. Több matroid esetén a probléma APX-nehézzé
válik. Egy természetes megközelítés az egyes matroidokhoz tartozó
függetlenségi poliéderek metszetének felírása, majd a metszet egy pontjának
megfelelő módon történő kikerekítése. Ismert, hogy a kapott LP feladat
egészértékűségi rése k matroid esetén legalább k-1, és a mohó algoritmus
mutatja, hogy legfeljebb k. Az előadáson Linhares, Olver, Swamy és
Zenklusen "Approximate Multi_matroid Intersection via Iterative Refinement"
c. cikkét áttekintve megmutatjuk, hogy k=3 esetén a kérdéses rés pontosan 2.
Ezáltal 2-approximációt adunk 3 matroid maximális közös független
halmazának a megkeresésére.