The set-covering problem

From Algorithm Wiki
Jump to navigation Jump to search

Problem Description

Given a universe U of n elements, a collection of subsets of U say S = {S1, S2…,Sm} where every subset Si has an associated cost. Find a minimum cost subcollection of S that covers all elements of U.

It was one of Karp’s NP-complete problems, shown to be so in 1972. Other applications: edge covering, vertex cover Interesting example: IBM finds computer viruses (wikipedia) Elements- 5000 known viruses Sets- 9000 substrings of 20 or more consecutive bytes from viruses, not found in ‘good’ code. A set cover of 180 was found. It suffices to search for these 180 substrings to verify the existence of known computer viruses.

Bounds Chart

File:The set-covering problemBoundsChart.png

Step Chart

File:The set-covering problemStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial [ Naive algorithm (1940)]

[ Random Split Exponential algorithm (1940)]

Horowitz and Sahni (1974)

[- dynamic programming algorithm (1956)]

Psinger; 1999 (1999)

Koiliaris and Xu 2015 (2015)

Bringmann 2017 (2017)

[ Pisinger 2003 (2003)]

Faaland 1973 (1973)

[ Pferschy 1999 (1999)]

[ Klinz 1999 (1999)]

[ Epstein 1997 (1997)]

[ Serang 2014 (2014)]

[ Serang 2015 (2015)]

[ Lokshtanov (2010)]

Polynomial > 3
Cubic
Quadratic
nlogn
Linear
logn