patternMinor
Clarification on NP-hardness and hardness of approximation results for set cover?
Viewed 0 times
clarificationapproximationhardnessforandresultscoverset
Problem
I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements.
I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it describes a worse case scenario. In other words, if I am only considering set cover for say the case that the number of subsets is less than the number of elements in the ground set (or vice versa), can I say that this case falls under a 'hard' or 'easy' case of set cover.
Moreover, in looking at the work by Dinur and Steurer 2013 , they say it is NP-hard to approximate set cover within a factor of $(1−\epsilon)ln (n)$, where $n$ is the size of the universe, but they don't mention the size of the collection of subsets (denote $m$), does this imply that this inapproximability result should hold for any $m$, regardless of it $m n$?
I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it describes a worse case scenario. In other words, if I am only considering set cover for say the case that the number of subsets is less than the number of elements in the ground set (or vice versa), can I say that this case falls under a 'hard' or 'easy' case of set cover.
Moreover, in looking at the work by Dinur and Steurer 2013 , they say it is NP-hard to approximate set cover within a factor of $(1−\epsilon)ln (n)$, where $n$ is the size of the universe, but they don't mention the size of the collection of subsets (denote $m$), does this imply that this inapproximability result should hold for any $m$, regardless of it $m n$?
Solution
When you have a result like "It is NP-hard to approximate X within ..." or say "X is NP-complete", it means that there is an infinite family of instances of X that are hard. This is what worst case intractability means.
In your example, the hardness of approximation result holds for the set cover problem, meaning that there is an infinite family of instances of set cover that are hard to approximate.
At this point, you might put further constraints on a problem in the form of "suppose every set satisfies this property" or whatever, but this is then a different problem, i.e., you are narrowing down on the instances that you care about. If you have a statement that says "set cover with your favorite property is NP-hard to approximate", it means that there is (still!) an infinite family of instances of this problem that remain hard.
In your example, the hardness of approximation result holds for the set cover problem, meaning that there is an infinite family of instances of set cover that are hard to approximate.
At this point, you might put further constraints on a problem in the form of "suppose every set satisfies this property" or whatever, but this is then a different problem, i.e., you are narrowing down on the instances that you care about. If you have a statement that says "set cover with your favorite property is NP-hard to approximate", it means that there is (still!) an infinite family of instances of this problem that remain hard.
Context
StackExchange Computer Science Q#106727, answer score: 2
Revisions (0)
No revisions yet.