3
$\begingroup$

We're covering the whole random universe $U$ of size $m$ with random sets $S_{1},\dots S_{n}$. I know that greedy set cover gives us a number between size of the minimal set cover and size of the minimal set cover multiplied by factor $H_{max\{|S_{i}|, \hspace{1 mm} for \hspace{1 mm} i=1,\dots, n\}}$ where $H_{i}$ is the $i-th$ harmonic number. My qestion is, what is the exact average number of sets we're going to get? Does the number of sets given by greedy behave as a normal distribution?

$\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.