bio | website | giovanniviglietta.com |
---|---|---|
location | Ottawa, Canada | |
age | 32 | |
visits | member for | 2 years |
seen | Feb 7 at 8:41 | |
stats | profile views | 79 |
Research Associate at Carleton University, Ottawa, working on distributed algorithms and computational geometry.
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 |