So I'm trying to solve this problem:
There are many people who apply for jobs at a company. Each applicant has some technical skills required for jobs. The skills possessed by different applicants may overlap. When hiring people, the company’s objective is to maximize the total numberof distinct skills possessed by the employees.
Design a $\left(1-\left(1-\frac{1}{p}\right)^{p}\right)$-approximation algorithm for selecting $p$ candidates from all the applicants.
And to be fair I'm really lost as to where to begin. I tried defining some probabilities like such:
Select $p$ candidates
Let $A$ = Pr{an applicant has at least one unique skill among the p candidates} = $\frac{1}{p}$.
Then $\overline A$ = $1-\frac{1}{p}$.
That is as far as I went in breaking down why we're given such a precise approximation algorithm. Any help would really be appreciated.


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.