Talk:Set cover problem
|WikiProject Computer science||(Rated C-class, Mid-importance)|
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 22.214.171.124 (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 126.96.36.199 (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
m and n
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 188.8.131.52 (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.
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?
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)