Giovanni Viglietta
Reputation
Next privilege 75 Rep.
Set bounties
 May 8 awarded Self-Learner May 8 awarded Teacher May 8 revised Hardness of approximation of Dominating Set added 1 characters in body May 8 awarded Scholar May 8 accepted Hardness of approximation of Dominating Set May 8 revised Hardness of approximation of Dominating Set added 3 characters in body May 8 revised Hardness of approximation of Dominating Set added 613 characters in body May 8 answered Hardness of approximation of Dominating Set May 7 comment Hardness of approximation of Dominating Set I agree this is sort of confusing. I guess this is why people tend to say nonchalantly that Set Cover and Dominating Set are equivalent as approximation problems (because they L-reduce to each other), and THEREFORE Dominating Set is not approximable within $\Omega(\log n)$, either. Well, these are two different $n$'s, so we should pay attention... May 7 revised Hardness of approximation of Dominating Set deleted 67 characters in body May 7 revised Hardness of approximation of Dominating Set added 8 characters in body May 7 awarded Autobiographer May 7 awarded Editor May 7 revised Hardness of approximation of Dominating Set added 26 characters in body May 7 answered Hardness of approximation of Dominating Set May 7 comment Hardness of approximation of Dominating Set Using my notation, the problem size of Set Cover is $m\cdot n$. This is correct, but all the approximation bounds are always given just in terms of $n$. That is, there is a greedy algorithm that achieves a $\ln n$ approximation ratio (no $m$ involved), and it is NP-hard to achieve a $c\cdot\log n$ approximation ratio (no $m$ involved). Hence, when reducing to Dominating Set, $n$ cannot be the number of vertices, but should be its logarithm. May 6 awarded Student May 6 asked Hardness of approximation of Dominating Set