{"id":8590,"date":"2014-12-07T10:44:52","date_gmt":"2014-12-07T18:44:52","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8590"},"modified":"2026-09-30T09:15:26","modified_gmt":"2026-09-30T17:15:26","slug":"set-cover-local","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-local\/","title":{"rendered":"Greedy Set Cover III: weighted H(d)-approximation via localizing"},"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>Strengthening the approximation ratio to <script type=\"math\/tex;\">{\\rm H}(d)<\/script> by \u201clocalizing\u201d the analysis.<\/em><\/center><\/p><\/blockquote>\n<p> Applying the <script type=\"math\/tex;\">{\\rm H}(n)<\/script>-approximation result to the \u201clocal\u201d subproblem for each set strengthens the approximation ratio to <script type=\"math\/tex;\">{\\rm H}(d)<\/script>, where <script type=\"math\/tex;\">d=\\max _s |s|<\/script> is the maximum set size, matching the classical bound<!--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\/set-cover-weighted\">Set Cover (weighted): H(n)-approximation via random stopping time<\/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\">Localized rounding scheme for 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\">0.<\/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\">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 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\">3.<\/td>\n<td style=\"padding-left:0em\"> <em>Return the sets that, when chosen, contained not-yet-covered elements.<\/em> <\/td>\n<\/tr>\n<\/table>\n<p>Note that the localized rounding scheme returns only \u201cuseful\u201d sets. <\/p>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Lemma.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>The localized rounding scheme returns a cover of expected cost at most <script type=\"math\/tex;\">\\sum _s c_s\\,  x^*_s\\,  {\\rm H}(|s|)<\/script>, which is at most <script type=\"math\/tex;\">{\\rm H}(d)~ c\\cdot x^*<\/script>, where <script type=\"math\/tex;\">d=\\max _s |s|<\/script> is the maximum set size. <\/p>\n<\/div><\/div>\n<p> <span style=\"float:right;margin:0.8em;margin-right:-0.5in;\"> <img decoding=\"async\" src=\"http:\/\/algnotes.info\/b\/wp-content\/uploads\/2014\/12\/img-00015.png\" alt=\"\\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=0.8in]{shared\/graphics\/set_cover_localized}\" style=\"width:0.8in\" class=\"zoooom\" \/> <\/span>\u00a0 <\/p>\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>For any set <script type=\"math\/tex;\">s<\/script>, define <script type=\"math\/tex;\">{\\cal I}_s<\/script> to be the weighted Set Cover instance obtained from <script type=\"math\/tex;\">{\\cal I}<\/script> by deleting all elements other than those in <script type=\"math\/tex;\">s<\/script>, giving <script type=\"math\/tex;\">s<\/script> cost 1, and giving all other sets cost 0. By <a href=\"http:\/\/algnotes.info\/on\/set-cover-weighted\">the analysis of the original (non-localized) rounding scheme<\/a>, if we apply that rounding scheme to <script type=\"math\/tex;\">{\\cal I}_s<\/script> (with fractional solution <script type=\"math\/tex;\">x^*<\/script>), the probability that <script type=\"math\/tex;\">s<\/script> is chosen is at most <script type=\"math\/tex;\">{\\rm H}(|s|) x^*_s<\/script>. <\/p>\n<p>Since that rounding scheme chooses <script type=\"math\/tex;\">s<\/script> with exactly the same probability that the localized rounding scheme chooses <script type=\"math\/tex;\">s<\/script>, the probability that the localized rounding scheme puts <script type=\"math\/tex;\">s<\/script> in the final cover is also at most <script type=\"math\/tex;\">{\\rm H}(|s|) x^*_s<\/script>. By linearity of expectation, summing over the sets, the expected cost of the cover returned by the localized scheme is at most <script type=\"math\/tex;\">\\sum _s c_s\\, {\\rm H}(|s|)\\, x^*_s<\/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 obtain 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\">Greedy algorithm for Set Cover (weighted): H(d)-approximation via localization<\/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 apply the method of conditional probabilities, we need a pessimistic estimator <script type=\"math\/tex;\">\\phi _t<\/script> for the cost of the final cover. Following the existence proof, we simply sum the pessimistic estimators for the individual sets, where for each set <script type=\"math\/tex;\">s<\/script> we use the pessimistic estimator <script type=\"math\/tex;\">\\phi ^s_t<\/script> for the original, non-localized rounding scheme for <script type=\"math\/tex;\">s<\/script>\u2019s subproblem <script type=\"math\/tex;\">{\\cal I}_s<\/script>: <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t ~ =~  \\sum _s c_s\\,  \\phi ^s_t ~ =~  \\sum _s c_s\\big({\\rm H}(n^s_t) x^*_s ~ +~ [s\\in S_t]\\big),  <\/script><\/div>\n<p> where <script type=\"math\/tex;\">S_t<\/script> contains the sets that were sampled in the first <script type=\"math\/tex;\">t<\/script> iterations and, when sampled, contained not-yet-covered elements, while <script type=\"math\/tex;\">n^s_t<\/script> is the number of elements in <script type=\"math\/tex;\">s<\/script> not covered by the end of iteration <script type=\"math\/tex;\">t<\/script>. (Note <script type=\"math\/tex;\">{\\rm H}(n^s_t) = {\\rm H}(0)=0<\/script> for <script type=\"math\/tex;\">s\\in S_t<\/script>.) <\/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;\">\\sum _s c_s x^*_s {\\rm H}(|s|)<\/script>.<\/em> (By inspection.) <\/p>\n<p>2. <em>The pessimistic estimator is a super-martingale w.r.t.\u00a0the localized rounding scheme.<\/em> <\/p>\n<p>This holds simply because the estimator is a sum of pessimistic estimators, each of which we already know is a super-martingale with respect to the original rounding scheme applied to <script type=\"math\/tex;\">{\\cal I}_s<\/script>, and we know that scheme treats the set <script type=\"math\/tex;\">s<\/script> the same as the localized rounding scheme. <\/p>\n<p>To verify, suppose iteration <script type=\"math\/tex;\">t<\/script> samples set <script type=\"math\/tex;\">s'<\/script>. Then, in the case that <script type=\"math\/tex;\">n^t_{s'} = 0<\/script>, the increase in the pessimistic estimator is zero. Otherwise, following the non-localized analysis, the increase is at most <\/p>\n<div id=\"desired\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{desired} c_{s'} \\, -\\,  \\sum _{s\\, :\\, n^s_t\\gt 0} \\frac{n^s_{t-1} - n^s_{t}}{n^s_{t-1}} c_s x^*_s. \\end{equation}<\/script><\/div>\n<p> Recall that <script type=\"math\/tex;\">\\textrm{E}[n^s_{t-1} - n^s_t \\, |\\, n^s_{t-1}]<\/script> is at least <script type=\"math\/tex;\">n^{s}_{t-1}\/|x^*|<\/script>, while <script type=\"math\/tex;\">\\textrm{E}[c_{s'}] = \\sum _s x^*_s c_s<\/script>. Hence, in expectation\u00a0\\eqref{desired} is non-positive. <\/p>\n<p>3. <em>If the final value of the pessimistic estimator is at most its initial value, then the outcome is a success.<\/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. The algorithm chooses a set <script type=\"math\/tex;\">s'<\/script> in iteration <script type=\"math\/tex;\">t<\/script> to minimize <script type=\"math\/tex;\">c_{s'}\/n^{s'}_t<\/script>. Let <script type=\"math\/tex;\">\\tilde s<\/script> contain the elements in <script type=\"math\/tex;\">s'<\/script> are not covered by sets in <script type=\"math\/tex;\">S_t<\/script> (so <script type=\"math\/tex;\">|\\tilde s| = n^{s'}_t<\/script>). <\/p>\n<p>With this choice of <script type=\"math\/tex;\">s'<\/script>, the bound\u00a0\\eqref{desired} is <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{align*}  c_{s'} {\\, {-}\\, }\\displaystyle \\sum _{s\\, :\\, n^s_t\\gt 0} \\sum _{e\\in \\tilde s\\cap s} c_s x^*_s \/ n^s_t ~  & =~  c_{s'} {\\, {-}\\, }\\displaystyle \\sum _{e\\in \\tilde s} \\sum _{s\\ni e} c_s x^*_s \/ n^s_t & (\\text{as } n^s_t - n^s_{t+1} = |\\tilde s\\cap s|) \\\\ & {\\, {\\le }\\, }~  c_{s'} {\\, {-}\\, }\\displaystyle (c_{s'}\/n_t^{s'}) \\sum _{e\\in \\tilde s} \\sum _{s\\ni e} x^*_s & (\\text{by the choice of } s') \\\\ & {\\, {\\le }\\, }~  c_{s'} {\\, {-}\\, }\\displaystyle (c_{s'}\/n_t^{s'}) \\sum _{e\\in \\tilde s} 1 & (\\text{by the feasibility of } x) \\\\ & =~  0 & (\\text{as } |\\tilde s| = n^{s'}_t). \\end{align*}<\/script><\/div>\n<p> Thus, the algorithm keeps the pessimistic estimator from increasing. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>The algorithm keeps the pessimistic estimator from increasing at each step. A slightly refined variant of Chv\u00e1tal\u2019s performance guarantee follows as a corollary: <\/p>\n<div id=\"a0000000012\" 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;\">\\sum _s x^*_s c_s {\\rm H}(|s|)<\/script>, where <script type=\"math\/tex;\">x^*<\/script> is any fractional set cover. This is at most <script type=\"math\/tex;\">{\\rm H}(d)~ c\\cdot x^*<\/script>, where <script type=\"math\/tex;\">d=\\max _s |s|<\/script> is the maximum set size and <script type=\"math\/tex;\">c\\cdot x^*<\/script> is the minimum cost of any fractional cover. <\/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=\"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>Strengthening the approximation ratio to by \u201clocalizing\u201d the analysis. Applying the -approximation result to the \u201clocal\u201d subproblem for each set strengthens the approximation ratio to , where is the maximum set size, matching the classical bound<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8640,"menu_order":3,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8590","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8590","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=8590"}],"version-history":[{"count":4,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8590\/revisions"}],"predecessor-version":[{"id":9015,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8590\/revisions\/9015"}],"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=8590"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}