HW6 Problem 4d

While writing up the solutions to HW6, it occurred to me that Problem 4 part d might be a little ambiguous, since we never discussed approximation algorithms with randomization. For the purposes of this problem, let's allow a small failure probability: your algorithm should in polynomial time return a valid set cover with high probability (say, at least 1 - 1/n) and in expectation the cost of the solution it returns should be at most O(log n) more than the cost of the optimum solution. Once you have this it's pretty simple to get to other versions (e.g. algorithms that always return a valid set cover but only run in polynomial time in expectation), so it's fine if you end with a statement of this form (again: in polynomial time, with high probability we return a set cover and in expectation it does not cost much more than the optimum solution).