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



Set Cover:Greedy vs LP
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 sub-constant error-probability low-degree test, and a sub-constant error-probability 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.


