{"id":8594,"date":"2014-12-07T10:45:20","date_gmt":"2014-12-07T18:45:20","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8594"},"modified":"2026-09-30T09:15:48","modified_gmt":"2026-09-30T17:15:48","slug":"set-cover-weighted","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-weighted\/","title":{"rendered":"Greedy Set Cover II: weighted H(n)-approximation via random stopping time"},"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 Chv\u00e1tal\u2019s greedy algorithm for weighted 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 Chv\u00e1tal\u2019s greedy algorithm for weighted Set Cover, and a proof that it is an <script type=\"math\/tex;\">{\\rm H}(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<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-unweighted\">Derivation for unweighted 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\">Rounding scheme for weighted 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> weighted 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\">1.<\/td>\n<td style=\"padding-left:0em\"> Compute a min-cost fractional set cover <script type=\"math\/tex;\">x^*<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/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\">3.<\/td>\n<td style=\"padding-left:1em\"> Choose a set randomly 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\">4.<\/td>\n<td style=\"padding-left:0em\"> Return the chosen sets. <\/td>\n<\/tr>\n<\/table>\n<p>Recall that <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> and <script type=\"math\/tex;\">{\\rm H}(n)<\/script> is <script type=\"math\/tex;\">1+1\/2+\\cdots + 1\/n<\/script>, about <script type=\"math\/tex;\">0.5+\\ln n<\/script>. <\/p>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (existence).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> With non-zero probability the rounding scheme returns a cover of cost at most <script type=\"math\/tex;\">{\\rm H}(n)<\/script> times the cost of the fractional set cover <script type=\"math\/tex;\">x^*<\/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>Let random variable <script type=\"math\/tex;\">T<\/script> be the number of draws until all <script type=\"math\/tex;\">n<\/script> elements are covered, and let r.v.\u00a0<script type=\"math\/tex;\">n_t<\/script> be the number of elements not yet covered after <script type=\"math\/tex;\">t\\le T<\/script> samples. <\/p>\n<p>Let <script type=\"math\/tex;\">c_s<\/script> denote the cost of set <script type=\"math\/tex;\">s<\/script>. The expected cost of each sampled set is <script type=\"math\/tex;\">\\sum _s c_s x^*_s \/ |x^*|<\/script>, that is, <script type=\"math\/tex;\">c\\cdot x^* \/ |x^*|<\/script>. By <a href=\"http:\/\/algnotes.info\/on\/walds\">Wald\u2019s equation<\/a>, the expected cost of the chosen sets is <script type=\"math\/tex;\">\\textrm{E}[T]\\,  c\\cdot x^*\/|x^*|<\/script>. <\/p>\n<p>The fractional cover <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 each randomly sampled set covers <script type=\"math\/tex;\">e<\/script> with probability at least <script type=\"math\/tex;\">1\/|x^*|<\/script>. Hence, in expectation the number of uncovered elements reduces by at least a factor of <script type=\"math\/tex;\">1-1\/|x^*|<\/script> with each sample: <\/p>\n<div id=\"eqn\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqn} \\textrm{E}[n_t - n_{t+1} \\, |\\, n_t] ~ \\ge ~  n_t\/|x^*|. \\end{equation}<\/script><\/div>\n<p> By <a href=\"http:\/\/algnotes.info\/on\/walds-dependent\">Wald\u2019s equation for dependent decrements<\/a>, bound\u00a0\\eqref{eqn} implies that the expected number of sampled sets, <script type=\"math\/tex;\">\\textrm{E}[T]<\/script>, is at most <script type=\"math\/tex;\">|x^*|\\, {\\rm H}(n)<\/script>. <\/p>\n<p>Hence, the expected cost of the chosen sets is at most the product <script type=\"math\/tex;\">{\\rm H}(n)\\, c\\cdot x^*<\/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 following algorithm. <\/p>\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=\"a0000000007\">H(n)-approximation via random stopping time<\/h1>\n<table id=\"a0000000008\" 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> weighted 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\">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 <script type=\"math\/tex;\">s<\/script> minimizing the cost of <script type=\"math\/tex;\">s<\/script> divided by the number of elements in <script type=\"math\/tex;\">s<\/script> 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 use the following pessimistic estimator <script type=\"math\/tex;\">\\phi _t<\/script> for the expectation of the final cost, conditioned on the state at the end of a given iteration <script type=\"math\/tex;\">t\\le T<\/script>: <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t ~ =~  {\\rm H}(n_t) \\, c\\cdot x^*\/|x^*| ~ +~ \\sum _{s\\in S_t} c_s,  <\/script><\/div>\n<p> where <script type=\"math\/tex;\">S_t<\/script> contains the first <script type=\"math\/tex;\">t<\/script> sets chosen. The second term in <script type=\"math\/tex;\">\\phi _t<\/script> is the cost of the sets chosen so far. The first term is an upper bound on the expected cost of the sets remaining to be chosen before all remaining elements are covered (because each iteration costs <script type=\"math\/tex;\">c\\cdot x^*\/|x^*|<\/script> in expectation, and we expect at most <script type=\"math\/tex;\">|x^*| {\\rm H}(n_t)<\/script> more iterations). <\/p>\n<div class=\"expandable\" id=\"a0000000010\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for verification of the pessimistic estimator\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for verification of the pessimistic estimator\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> 1. <em>The pessimistic estimator is initially <script type=\"math\/tex;\">{\\rm H}(n) c\\cdot x^*<\/script>.<\/em> (By inspection). <\/p>\n<p>2. <em>The pessimistic estimator is a super-martingale w.r.t.\u00a0the rounding scheme.<\/em> <\/p>\n<p>When a set <script type=\"math\/tex;\">s'<\/script> is chosen in iteration <script type=\"math\/tex;\">t<\/script>, the increase <script type=\"math\/tex;\">\\phi _{t} - \\phi _{t-1}<\/script> equals <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\">  c_{s'} ~ -~  ({\\rm H}(n_{t-1}) - {\\rm H}(n_{t})) c\\cdot x^*\/|x^*|.  <\/script><\/div>\n<p> Using <script type=\"math\/tex;\">{\\rm H}(b) - {\\rm H}(a) \\ge (b-a)\/a<\/script>, the increase is at most <\/p>\n<div id=\"desired\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{desired} c_{s'} \\, -\\,  \\frac{n_{t-1} - n_{t}}{n_{t-1}}\\, c\\cdot x^*\/|x^*|. \\end{equation}<\/script><\/div>\n<p> For a set <script type=\"math\/tex;\">s'<\/script> chosen randomly from <script type=\"math\/tex;\">x^*\/|x^*|<\/script>, the bound\u00a0\\eqref{desired} is non-positive in expectation, because <script type=\"math\/tex;\">\\textrm{E}[c_{s'}] = c\\cdot x^*\/|x^*|<\/script> while <script type=\"math\/tex;\">\\textrm{E}[n_t - n_{t+1}] \\ge n_t\/|x^*|<\/script>. <\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:6px\"><\/div>\n<\/p>\n<p>3. <em>If the final value of the pessimistic estimator is at most <script type=\"math\/tex;\">{\\rm H}(n)c\\cdot x^*<\/script>, then the outcome is successful.<\/em> (By inspection.) <\/p>\n<hr \/>\n<p>Now that we\u2019ve verified the pessimistic estimator, we verify that the algorithm keeps it from increasing at each step. As observed above, the expectation of\u00a0\\eqref{desired} is non-positive. Hence, there exists a set <script type=\"math\/tex;\">s'<\/script> making it non-positive. Gathering terms that depend on <script type=\"math\/tex;\">s'<\/script> (namely <script type=\"math\/tex;\">c_{s'}<\/script> and <script type=\"math\/tex;\">n_{t}<\/script>), it is non-positive iff <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\frac{c_{s'}}{n_{t-1} - n_{t}} \\, \\le \\, \\frac{|x^*|}{n_{t-1}\\,  c\\cdot x^*\/|x^*|}. <\/script><\/div>\n<p> Some set <script type=\"math\/tex;\">s'<\/script> satisfies this, so the algorithm\u2019s choice of <script type=\"math\/tex;\">s'<\/script> (which minimizes the left-hand side) must do so. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>The algorithm keeps the pessimistic estimator from increasing, ensuring a successful outcome (see the verification of the pessimistic estimator for details). The well-known performance guarantee follows as a corollary: <\/p>\n<div id=\"a0000000013\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b>Theorem <\/b> (<span class=\"cite\">[<a href=\"#Chvatal79Greedy\">1<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The algorithm above returns a cover of cost at most <script type=\"math\/tex;\">{\\rm H}(n)<\/script> times the minimum cost of any fractional set cover, where <script type=\"math\/tex;\">n<\/script> is the number of elements. <\/p>\n<\/div><\/div>\n<p>The <a href=\"http:\/\/algnotes.info\/on\/set-cover-local\">next note<\/a> discusses the stronger bound of <script type=\"math\/tex;\">{\\rm H}(d)<\/script>, where <script type=\"math\/tex;\">d=\\max _s |s|<\/script>. <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000014\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-markov\"><script type=\"math\/tex;\">O(\\log n)<\/script>-approximation for weighted Set Cover without Wald\u2019s<\/a>: analyzing the rounding scheme at a fixed stopping time is possible, but yields a different algorithm and weaker performance guarantee. <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Set_cover_problem\">Set cover problem<\/a> (wikipedia) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Vaclav_Chvatal\">V\u00e1clav Chv\u00e1tal<\/a> (wikipedia) <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/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=\"Chvatal79Greedy\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;V+Chvatal&quot;+intitle:&quot;+A+greedy+heuristic+for+the+set-covering+problem&quot;\">V.\u00a0Chv\u00e1tal. A greedy heuristic for the set-covering problem. <em>Math. Operations Research<\/em>, 4(3):233\u2013235, 1979. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Randomized rounding yields Chv\u00e1tal\u2019s greedy algorithm for weighted 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 Chv\u00e1tal\u2019s greedy algorithm for weighted Set Cover, and a proof that it is an -approximation algorithm.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8640,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8594","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8594","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=8594"}],"version-history":[{"count":3,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8594\/revisions"}],"predecessor-version":[{"id":9022,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8594\/revisions\/9022"}],"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=8594"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}