2
$\begingroup$

According to the wikipedia page for Set Cover, the greedy algorithm for weighted set cover achieves the polynomial-time approximation bound. There are other techniques for solving Set Cover, such as randomized rounding of a linear programming relaxation, which I believe achieve the same asymptotic bound.

Is there information comparing these asymptotically-equivalently-performing algorithms in practice?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.