Talk:Set cover problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.

What does it mean to call the decision problem NP-complete and the optimization problem NP-hard? NP-hardness refers to decision problems. Isn't #P-completeness the notion we are after for the optimization part?

NP-Complete means that the problem is both NP-Hard (harder than any other problem in NP) as well as in NP (meaning a given solution can be verified in polynomial time). We can verify that a solution to the decision problem is valid in polynomial time (by simply checking if there are at most k sets used in the solution, and whether those sets actually do cover U). However, it is more difficult to verify a solution to the optimization problem, as we have to check whether the given solution is in fact the optimal one (which can't be done in polynomial time). This means the optimization problem is not in NP, and therefore cannot be NP-Complete. So no, NP-hardness does not always refer to decision problems. —Preceding unsigned comment added by (talk) 02:45, 22 April 2008 (UTC)

NP is a class of decision problems, so an optimization problem cannot be in NP *by definition*. Your argument is a red herring (in particular since it is probably difficult to prove that deciding whether a given solution is optimal cannot be done in polynomial time). --Mellum (talk) 12:35, 12 May 2008 (UTC)

I believe that set packing and hitting set are duals of one another, not set cover and hitting set, as indicated in "related problems." Set cover and hitting set are both minimization problems. —Preceding unsigned comment added by (talk) 16:12, 4 September 2008 (UTC)

True. I corrected that and added a template Template:Covering-Packing_Problem_Pairs with the goal to collect all important covering problems together with their LP-dual problems. ylloh (talk) 17:50, 11 March 2009 (UTC)

Hitting set and set cover[edit]

There is some discussion related to this page at Talk:Vertex cover#Merge hitting set to set cover?; comments welcome. — Miym (talk) 14:49, 11 November 2009 (UTC)


Thanks for fixing my change Miym, i must have misclicked in some way. —Preceding unsigned comment added by (talk) 14:22, 30 November 2009 (UTC)

m and n[edit]

Hi everyone, There is a mistake in this article: the universe should contain n elements instead of m, and the collection of subsets should be of size m instead of n. This way, the approximability and inapproximability section become correct. — Preceding unsigned comment added by (talk) 20:56, 8 May 2012 (UTC)


The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard.

Isn't the optimization version NP-complete, too? — Preceding unsigned comment added by (talk) 08:51, 8 March 2013 (UTC)

How can the optimization version not be NP-complete if it can be formulated as a 0-1 integer linear program (which is NP-complete)?

Over-emphasis of inapproximability?[edit]

There are countless pages on the internet where people ask for algorithms for set cover and get told to use the greedy algorithm, some quoting this article "Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover". The "best possible" referred to here is only according to criteria interesting to someone involved in complexity theory-- it's talking about approximation error in the _worse cast_. Practical problems that people are usually trying to solve are not usually pathological, and often the greedy algorithm does not do very well (in terms of fitness of the solution) compared to integer linear programming techniques. Personally, I find the results from complexity theory fascinating, but usually completely irrelevant for the set cover problems that arise as sub-problems in engineering. --Gmaxwell (talk) 05:06, 27 October 2015 (UTC)