Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

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

  1. You can view the standard greedy set cover algorithm as a derandomization (using the method of conditional probabilities) of the following randomized rounding of the LP solution $x$: repeatedly sample sets from the distribution defined by $x/\|x\|_1$ until the sets form a cover. For details, see here or here.

  2. Although greedy algorithms are often faster and easier to implement than solving the LP and rounding it, in practice, solving and rounding the LP might well give you better results, especially for "easy" instances for which many coordinates of the LP turn out to be integral.

share|improve this answer
    
Hi Neal, welcome to MO. You don't yet have enough reputation to comment, but keep answering questions and you will in time :) –  David Roberts Nov 5 '12 at 9:20
    
Thanks @DavidRoberts. –  Neal Nov 5 '12 at 16:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.