Hi
Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches?
thanks
Hi Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches? thanks 


Both greedy and LP are asymptotically optimal approximations. According to a well known result by Ran and Shmuel, getting a better than c log(n) approximation of set cover is equivalent to showing that P = NP. Here is a reference: Ran, Shmuel (1997), "A subconstant errorprobability lowdegree test, and a subconstant errorprobability PCP characterization of NP", STOC '97 In practical terms, they end up doing effectively the same thing, just that linear programming gives a slightly more general perspective on the problem. This is similar to the idea of thinking of network flow as either a special kind of combinatorial graph optimization problem; or thinking of it more generally as another instance of linear programming. The linear programming perspective is often useful for proving some things and connecting results together (for example via duality), while the greedy method suggests a more practical route to implementation and illuminates some of the specific details about the set cover problem. 


This is really a comment, not an answer, but for whatever reason I see no comment field.


