{"id":8592,"date":"2014-12-07T10:45:07","date_gmt":"2014-12-07T18:45:07","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8592"},"modified":"2026-09-30T09:15:44","modified_gmt":"2026-09-30T17:15:44","slug":"set-cover-unweighted","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-unweighted\/","title":{"rendered":"Greedy Set Cover I: unweighted ln(n)-approximation"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<blockquote class=\"quote\"><p><center><em>Randomized rounding yields the Johnson\/Lov\u00e1sz greedy algorithm for unweighted Set Cover.<\/em><\/center><\/p><\/blockquote>\n<p> The rounding scheme samples sets i.i.d.\u00a0from the fractional cover until all elements are covered. Applying the method of conditional probabilities yields the Johnson\/Lov\u00e1sz greedy algorithm for unweighted Set Cover, and a proof that it is a <script type=\"math\/tex;\">\\ln (n)<\/script>-approximation algorithm.<!--more--><\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/p>\n<hr \/>\n<div class=\"expandable\" id=\"a0000000002\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for background material\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for background material\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">About oblivious randomized rounding<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/greedy-example\">The greedy Set-Cover algorithm<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/randomized-rounding\">Randomized rounding<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/method-of-conditional-probabilities\">The method of conditional probabilities<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/pessimistic-estimators\">Pessimistic estimators<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/modeling\">Fractional set cover<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<\/div>\n<hr \/>\n<\/p>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000003\">Randomized-rounding scheme for unweighted Set Cover<\/h1>\n<table id=\"a0000000004\" class=\"latex-scheme\" cellspacing=\"0\" cellpadding=\"4\" width=\"100%\" style=\"border-top:1px solid #CCC;border-bottom:1px solid #CCC;margin-top:2ex;margin-bottom:2ex;\">\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">&nbsp;<\/td>\n<td style=\"padding-left:0em\"><b style=\"font-size:90%\">input:<\/b> Set-Cover instance <script type=\"math\/tex;\">{\\cal I}<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">&nbsp;<\/td>\n<td style=\"padding-left:0em\"><b style=\"font-size:90%\">output:<\/b> set cover for <script type=\"math\/tex;\">{\\cal I}<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">0.<\/td>\n<td style=\"padding-left:0em\"> Compute a <a href=\"http:\/\/algnotes.info\/on\/modeling\">fractional set cover<\/a> <script type=\"math\/tex;\">x^*<\/script> minimizing <script type=\"math\/tex;\">|x^*|<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Repeat until the sampled sets form a cover: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:1em\"> Sample a random set from the distribution defined by <script type=\"math\/tex;\">x^*\/|x^*|<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> Return the sampled sets. <\/td>\n<\/tr>\n<\/table>\n<p> Note: <script type=\"math\/tex;\">|x^*|<\/script> denotes the 1-norm <script type=\"math\/tex;\">\\sum _s x^*_s<\/script> of <script type=\"math\/tex;\">x^*<\/script>. <\/p>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (existence,\u00a0<span class=\"cite\">[<a href=\"#Young95Randomized\">3<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Let <script type=\"math\/tex;\">n\\gt 1<\/script> be the number of elements. With non-zero probability the rounding scheme returns a set cover of size at most <script type=\"math\/tex;\">T = \\lceil |x^*| \\ln n\\rceil <\/script>. <\/p>\n<\/div><\/div>\n<div id=\"a0000000006\" class=\"latex-paragraph latex-proof\">\n<div class=\"latex-paragraph-heading\">  <b>Proof. <\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>The fractional solution <script type=\"math\/tex;\">x^*<\/script> gives total weight at least 1 to the sets containing any given element <script type=\"math\/tex;\">e<\/script>, so the probability that <script type=\"math\/tex;\">e<\/script> is covered in any given round is at least <script type=\"math\/tex;\">1\/|x^*|<\/script>. Hence, after <script type=\"math\/tex;\">T<\/script> rounds, the expected number of the <script type=\"math\/tex;\">n<\/script> elements left uncovered is at most <script type=\"math\/tex;\">n(1-1\/|x^*|)^T<\/script> which is strictly less than <script type=\"math\/tex;\">n\\exp (T\/|x^*|)<\/script>, which is 1 or less by the choice of <script type=\"math\/tex;\">T<\/script>. <\/p>\n<\/div>\n<div style=\"float:right;border:1px solid #444;width:0.45em;height:0.45em\">\u00a0<\/div>\n<div style=\"clear:both\">\u00a0<\/div>\n<\/p><\/div>\n<p>Next, we apply the method of conditional probabilities to derive the algorithm. <\/p>\n<div id=\"a0000000007\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (algorithm,\u00a0<span class=\"cite\">[<a href=\"#Young95Randomized\">3<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Applying the method of conditional probabilities to the existence proof yields the following algorithm. <\/p>\n<\/div><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000008\">Greedy algorithm for Set Cover (unweighted): ln(n)-approximation<\/h1>\n<table id=\"a0000000009\" class=\"latex-alg\" cellspacing=\"0\" cellpadding=\"4\" width=\"100%\" style=\"border-top:1px solid #CCC;border-bottom:1px solid #CCC;margin-top:2ex;margin-bottom:2ex;\">\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">&nbsp;<\/td>\n<td style=\"padding-left:0em\"><b style=\"font-size:90%\">input:<\/b> Set-Cover instance <script type=\"math\/tex;\">{\\cal I}<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">&nbsp;<\/td>\n<td style=\"padding-left:0em\"><b style=\"font-size:90%\">output:<\/b> set cover for <script type=\"math\/tex;\">{\\cal I}<\/script><\/p>\n<div style=\"margin:0pt;padding:0pt;margin-bottom:6px\"><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Repeat until the chosen sets form a cover: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:1em\"> Choose a set that contains a maximum number of elements that are not yet covered by chosen sets. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:0em\"> Return the chosen sets. <\/td>\n<\/tr>\n<\/table>\n<p>To derive the algorithm, we need an appropriate pessimistic estimator <script type=\"math\/tex;\">\\phi _t<\/script> for the expectation of the number of elements that will be left uncovered by the end of iteration <script type=\"math\/tex;\">T<\/script>, conditioned on the state at the end of a given iteration <script type=\"math\/tex;\">t\\le T<\/script>. Letting <script type=\"math\/tex;\">n_t<\/script> denote the number of elements remaining uncovered at the end of iteration <script type=\"math\/tex;\">t<\/script>, this conditional expectation is at most <\/p>\n<div id=\"eq\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{eqnarray} \\label{eq} \\phi _t ~ =~  n_t(1-1\/|x^*|)^{T-t}. \\end{eqnarray}<\/script><\/div>\n<div class=\"expandable\" id=\"a0000000010\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for verification of pessimistic estimator\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for verification of pessimistic estimator\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> 1. <em>The pessimistic estimator is initially less than 1.<\/em> <\/p>\n<p>By inspection <script type=\"math\/tex;\">\\phi _0<\/script> is <script type=\"math\/tex;\">n(1-1\/|x^*|)^T<\/script>, which was shown to be less than 1 in the existence proof. <\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:6px\"><\/div>\n<\/p>\n<p>2. <em>The pessimistic estimator is a super-martingale w.r.t.\u00a0the original randomized rounding scheme.<\/em> <\/p>\n<p>In iteration <script type=\"math\/tex;\">t<\/script>, choosing a set randomly from <script type=\"math\/tex;\">x^*\/|x^*|<\/script> makes <script type=\"math\/tex;\">E[n_t\\, |\\, n_{t-1}] \\le n_{t-1}(1-1\/|x^*|)<\/script>, because each of the <script type=\"math\/tex;\">n_{t-1}<\/script> elements not yet covered has probability at least <script type=\"math\/tex;\">1\/|x^*|<\/script> of being covered. Hence <script type=\"math\/tex;\">\\textrm{E}[\\phi _t\\, |\\, \\phi _{t-1}] \\le \\phi _{t-1}<\/script>. <\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:6px\"><\/div>\n<\/p>\n<p>3. <em>If the pessimistic estimator is less than 1 at the end, the outcome is a success.<\/em> <\/p>\n<p>Since <script type=\"math\/tex;\">\\phi _T= n_t<\/script>, if <script type=\"math\/tex;\">\\phi _T \\lt 1<\/script>, then all elements are covered by the first <script type=\"math\/tex;\">T<\/script> sets. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>The algorithm chooses the set that contains a maximum number of not-yet-covered elements. This choice also minimizes the resulting value of the pessimistic estimator. (The factor of <script type=\"math\/tex;\">(1-1\/|x^*|)^{T-t}<\/script> in <script type=\"math\/tex;\">\\phi _t<\/script> can be ignored, since it is independent of the choices made by the algorithm. Hence, minimizing <script type=\"math\/tex;\">\\phi _t<\/script> is the same as minimizing <script type=\"math\/tex;\">n_t<\/script>.) Hence, the algorithm guarantees a successful outcome. <\/p>\n<div id=\"a0000000011\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (<span class=\"cite\">[<a href=\"#Johnson74Approximation\">1<\/a>, <a href=\"#Lovasz75Ratio\">2<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> For unweighted set cover with <script type=\"math\/tex;\">n\\gt 1<\/script>, the greedy Set-Cover algorithm returns a cover of size at most <script type=\"math\/tex;\">\\lceil |x^*| \\ln n\\rceil <\/script>, where <script type=\"math\/tex;\">|x^*|<\/script> is the minimum size of any fractional cover and <script type=\"math\/tex;\">n<\/script> is the number of elements. <\/p>\n<\/div><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div>\n<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"Johnson74Approximation\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;D+S++Johnson&quot;+intitle:&quot;+Approximation+algorithms+for+combinatorial+problems&quot;\">D.\u00a0S. Johnson. Approximation algorithms for combinatorial problems. <em>J. Computer System Sciences<\/em>, 9:256\u2013278, 1974. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Lovasz75Ratio\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;L+Lovasz&quot;+intitle:&quot;+On+the+ratio+of+optimal+integral+and+fractional+covers&quot;\">L.\u00a0Lov\u00e1sz. On the ratio of optimal integral and fractional covers. <em>Discrete Mathematics<\/em>, 13:383\u2013390, 1975. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Young95Randomized\">3<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;N+E++Young&quot;+intitle:&quot;+Randomized+rounding+without+solving+the+linear+program&quot;\">N.\u00a0E. Young. Randomized rounding without solving the linear program. In <em>Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms<\/em>, pages 170\u2013178, San Francisco, California, 22\u201324\u00a0Jan. 1995. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Randomized rounding yields the Johnson\/Lov\u00e1sz greedy algorithm for unweighted Set Cover. The rounding scheme samples sets i.i.d.\u00a0from the fractional cover until all elements are covered. Applying the method of conditional probabilities yields the Johnson\/Lov\u00e1sz greedy algorithm for unweighted Set Cover, and a proof that it is a -approximation algorithm.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8640,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8592","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8592","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/comments?post=8592"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8592\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8640"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=8592"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}