Approximerbarheten hos problemet Minimum Hitting Set

Abstrakt:

Antag att vi har en mängd X och en familj C av delmängder till X, och vi vill välja ut en så liten delmängd S av X som möjligt under bivillkoret att varje mängd i C har något element med i S.

Detta problem kallas för Minimum Hitting Set och är NP-svårt att lösa exakt. När ett problem är svårt att lösa är exakt är det naturligt att försöka hitta en lösning som är ganska bra. Vi säger att en algoritm approximerar ett problem inom en faktor c om den producerar en lösning som är högst en faktor c större än den optimala. Hur lätt det är att hitta approximativa lösningar varierar enormt mellan olika NP-svåra problem. Ett viktigt problem inom teoretisk datalogi är att utreda olika problems approximationsegenskaper.

Det är känt att generella Minimum Hitting Set är rejält svårt att approximera. I detta seminarium koncentrerar vi oss på Minimum Hitting Set där mängderna i familjen C alla har samma storlek. Om mängderna har storlek k, säg, går detta problem att approximera inom en faktor k med en enkel algoritm. När k=2 är problemet ekvivalent med det välkända problemet Minimal Hörntäckning. Det tycks naturligt att problemt blir svårare när k växer, men upp till alldeles nyligen kunde man inte visa starkare icke-approximationsresultat för k>2 än för k=2.

Vi diskuterar utveckligen för detta problem och visar att när k är högst 4 så är problemet NP-svårt att approximera inom en faktor 2.